Algorithmic Aspects in Information and Management: 16th International Conference, AAIM 2022, Guangzhou, China, August 13–14, 2022, Proceedings (Lecture Notes in Computer Science, 13513)

This book constitutes the proceedings of the 16th International Conference on Algorithmic Aspects in Information and Management, AAIM 2022, which was held online during August 13-14, 2022. The conference was originally planned to take place in Guangzhou, China, but changed to a virtual event due to the COVID-19 pandemic. The 41 regular papers included in this book were carefully reviewed and selected from 59 submissions. Preface Organization Contents Approximation Algorithms A Binary Search Double Greedy Algorithm for Non-monotone DR-submodular Maximization 1 Introduction 2 Related Work 3 Preliminaries 4 Algorithm 5 Conclusions References An Approximation Algorithm for the Clustered Path Travelling Salesman Problem 1 Introduction 2 Preliminaries 3 Approximation Algorithms for the PSCP 4 Approximation Algorithm for the CPTSP 5 Discussion References Improved Approximation Algorithm for the Asymmetric Prize-Collecting TSP 1 Introduction 2 Preliminaries 3 Approximation Algorithms References Scheduling Problem and Game Theory Approximation Scheme for Single-Machine Rescheduling with Job Delay and Rejection 1 Introduction 2 Preliminaries 3 Dynamic Programming 4 A Fully Polynomial Time Approximation Scheme 5 Conclusion References Online Early Work Maximization Problem on Two Hierarchical Machines with Buffer or Rearrangements 1 Introduction 2 Preliminaries 3 Buffer Model 4 Rearrangement Model 5 Discussion References On-line Single Machine Scheduling with Release Dates and Submodular Rejection Penalties 1 Introduction 2 Preliminaries 3 1|rj,on-line,reject|Cmax+(R) 3.1 The Offline Problem 3.2 The On-line Algorithm 4 Conclusion References The Optimal Dynamic Rationing Policy in the Stock-Rationing Queue 1 Introduction 2 Model Description 3 Optimization Model Formulation 3.1 The States and Policies 3.2 The Stationary Probability Vector 3.3 The Reward Function 3.4 The Perturbation Realization Factor 3.5 The Penalty Cost 4 Monotonicity and Optimality 5 Concluding Remarks References The Constrained Parallel-Machine Scheduling Problem with Divisible Processing Times and Penalties 1 Introduction 2 Terminologies and Fundamental Lemmas 3 An Exact Algorithm to Solve the CPS-DTTP Problem 4 An Exact Algorithm to Solve the CPS-DTMP Problem 5 An Exact Algorithm to Solve the CPS-DTBP Problem 6 Conclusion and Further Work References Obnoxious Facility Location Games with Candidate Locations 1 Introduction 2 Definition and Terminology 3 Obnoxious Single Facility Location Game 4 Obnoxious Heterogeneous Two-facility Location Game 5 Conclusion References Nonlinear Combinatorial Optimization Streaming Adaptive Submodular Maximization 1 Introduction 2 Related Work 3 Preliminaries 3.1 Items 3.2 Policies 3.3 Problem Formulation and Additional Notations 4 Uniform Cost 4.1 Algorithm Design 4.2 Performance Analysis 4.3 Offline Estimation of favg(*) 5 Nonuniform Cost 5.1 Algorithm Design 5.2 Performance Analysis 5.3 Offline Estimation of favg(*) References Constrained Stochastic Submodular Maximization with State-Dependent Costs 1 Introduction 2 Preliminaries and Problem Formulation 3 Continuous Optimization Phase 4 Rounding Phase 4.1 Contention Resolution Scheme 4.2 Algorithm Design 4.3 Performance Analysis 4.4 Completing the Last Piece of the Puzzle: Discussion on and References Bicriteria Algorithms for Maximizing the Difference Between Submodular Function and Linear Function Under Noise 1 Introduction 2 Related Work 3 Preliminaries 4 The Bicriteria Algorithm Under Noise with the Cardinality Constraint 5 The Bicriteria Algorithm Under Noise with the Matroid Constraint 6 Conclusions References Monotone k-Submodular Knapsack Maximization: An Analysis of the Greedy+Singleton Algorithm 1 Introduction 2 Preliminaries 3 Approximations of Greedy+Singleton 4 Experiments 5 Conclusion References Guarantees for Maximization of k-Submodular Functions with a Knapsack and a Matroid Constraint 1 Introduction 2 Preliminaries 2.1 k-Submodular Function 2.2 k-Submodular Maximization with a Knapsack and a Matroid Constraint 2.3 Algorithm 3 Analysis for Non-monotone k-submodular Maximization with a Knapsack Constraint and a Matroid Constraint 4 Analysis for Monotone k-Submodular Maximization with a Knapsack and a Matroid Constraint 5 Discussion References Network Problems Defense of Scapegoating Attack in Network Tomography 1 Introduction 2 Problem Formulation 2.1 Network Tomography Model 2.2 Scapegoating Attack Model 3 Defense Strategy 3.1 What to Defend? 3.2 Key Observations 3.3 Defense Methodologies 3.4 Minimum Number Defending Path Generation 4 Performance Evaluation 4.1 Experiment Setup 4.2 Results of Defense Strategy 5 Conclusion References Adaptive Competition-Based Diversified-Profit Maximization with Online Seed Allocation 1 Introduction 2 Problem Formulation 2.1 The CIC Model 2.2 ACDM Problem 3 The Algorithm 4 Experiments Settings and Results 5 Conclusion References Collaborative Service Caching in Mobile Edge Nodes 1 Introduction 2 Related Work 3 Preliminary 3.1 System Model 3.2 Cache Services at Mobile Edge Nodes 3.3 The Cost of Serving at the Edge and the Remote Data Center 3.4 Pricing Strategy of the Edge and the Remote Data Center 3.5 The Utility of Serving at the Edge and the Remote Data Center 3.6 The Response Delay of the Edge and the Remote Data Center 4 Coalition Mechanism for the Collaborative Service Caching Problem with Service Sharing 4.1 Coalition Mechanism Among MENs 4.2 Mechanism Analysis 5 Approximation Algorithm for the Service Caching Problem 5.1 Problem Formulation 5.2 Randomized Algorithm 6 Simulation Results and Discussions 6.1 Experiment Settings 6.2 Performance Evaluation 7 Conclusion References A Decentralized Auction Framework with Privacy Protection in Mobile Crowdsourcing 1 Introduction 2 Crowdsourcing Model and Problem Formulation 2.1 Crowdsourcing Model 2.2 Formulation of Decentralized Auction 3 Design Rationales and Algorithms 4 Theoretical Analysis 5 Numerical Simulations 6 Related Works 7 Conclusion References Profit Maximization for Multiple Products in Community-Based Social Networks 1 Introduction 2 Related Work 3 Network Model and Problem Formulation 3.1 The Network Model 3.2 Problem Formulation 4 Solution for PMPMP 4.1 Properties of Profit Maximization Function f 4.2 Relaxation of Profit Function f 5 Experiments 5.1 Experimental Setup 5.2 Experimental Results 6 Conclusion References MCM: A Robust Map Matching Method by Tracking Multiple Road Candidates 1 Introduction 2 Problem Model 2.1 Point-to-Road Similarity 2.2 Trajectory-to-Route Similarity 3 Multiple Candidate Matching 3.1 Route Candidates 3.2 Updating the Sparse Score Matrix 3.3 MCM for Online Map Matching 4 Experiment 5 Conclusion and Future Work References Pilot Pattern Design with Branch and Bound in PSA-OFDM System 1 Introduction 2 Channel Estimation in PSA-OFDM System 3 Pilot Pattern Design with Branch and Bound 3.1 Branch 3.2 Bound 4 Simulation Results 5 Conclusion References AoI Minimizing of Wireless Rechargeable Sensor Network Based on Trajectory Optimization of Laser-Charged UAV 1 Introduction 2 Related Works 3 Model and Problem Definition 3.1 Network Model 3.2 Data Transmission Model from Sensor to UAV 3.3 Energy Harvesting Model from UAV to Sensor 3.4 Laser Charging Model from LBD to UAV 3.5 Problem Formulation 4 Algorithm for the AoIO Problem 5 Performance Evaluation 6 Conclusion References Energy-Constrained Geometric Coverage Problem 1 Introduction 2 Preliminaries 3 Greedy Algorithm 4 Discussion References Incremental SDN Deployment to Achieve Load Balance in ISP Networks 1 Introduction 2 Network Model and Problem Formulation 2.1 Network Model and Problem Definition 2.2 Problem Formulation 3 Complexity and Inapproximability Analysis 3.1 Hardness of k-LB Problem 3.2 Inapproximability Analysis 4 Algorithm Design and Analysis 5 Numerical Evaluation 5.1 Experimental Setup 5.2 Maximum Link Utilization 5.3 Upgrade Percentage 5.4 Least Upgrade Percentage to Converge 5.5 Cumulative Distribution Function (CDF) 6 Conclusion References Graph Theory Polynomial Time Algorithm for k-vertex-edge Dominating Problem in Interval Graphs 1 Introduction 2 Preliminaries and Notation 3 The MIN-k-VEDS Algorithm for Interval Graphs 4 Correctness and Implementation of the Algorithm 5 Conclusion References Cyclically Orderable Generalized Petersen Graphs 1 Introduction 2 Cyclic Base Ordering of G(n,1) 2.1 The Case n=3m 2.2 The Case n=3m+1 2.3 The Case n=3m+2 3 Cyclic Base Ordering of G(n,2) 3.1 The Case n=3m for m2 3.2 The Case n=3m+1 for m2 3.3 The Case n=3m+2 for m2 4 Conclusion References The r-Dynamic Chromatic Number of Planar Graphs Without Special Short Cycles 1 Introduction 2 Reducible Configurations 3 Proof of Theorem 1.2 References Distance Magic Labeling of the Halved Folded n-Cube 1 Introduction 2 Preliminaries 3 Proof of Theorem 1 3.1 Proof of Theorem 1 (i) 3.2 Proof of Theorem 1 (ii) References Balanced Graph Partitioning Based on Mixed 0-1 Linear Programming and Iteration Vertex Relocation Algorithm 1 Introduction 2 Related Work 3 Mixed 0-1 Linear Programming Model for Graph Partitioning 4 Iteration Algorithm 4.1 Variables Selection Strategy 4.2 Update Parameter 4.3 Iteration Vertex Relocation Algorithm 5 Experiments 5.1 Experimental Effect and Comparison 6 Conclusion References Partial Inverse Min-Max Spanning Tree Problem Under the Weighted Bottleneck Hamming Distance 1 Introduction 2 Preliminary 3 PIMMST Under the Weighted Bottleneck Hamming Distance 3.1 PIMMST with Value of Optimal Tree Restriction Under the Weighted Bottleneck Hamming Distance 3.2 PIMMST Under the Weighted Bottleneck Hamming Distance 4 CPIMMST Under the Weighted Bottleneck Hamming Distance 4.1 CPIMMST with Value of Optimal Tree Restriction Under the Weighted Bottleneck Hamming Distance 4.2 CPIMMST Under the Weighted Bottleneck Hamming Distance 5 Concluding References Mixed Metric Dimension of Some Plane Graphs 1 Introduction 2 Preliminaries 3 The Mixed Metric Dimension of Web Graph Wn 4 The Mixed Metric Dimension of Plane Graph (Convex Polytope) Dn 5 Conclusion References On the Transversal Number of k-Uniform Connected Hypergraphs 1 Introduction 1.1 Known Results 1.2 Our Results 2 The Upper Bound for Transversal Number 3 Extremal k-Uniform Connected Hypergraphs References An Improvement of the Bound on the Odd Chromatic Number of 1-Planar Graphs 1 Introduction 2 The Proof of Theorem 2 References Fast Searching on k-Combinable Graphs 1 Introduction 2 K-Combinable Graphs 3 Cacti Graphs 4 Cartesian Product of a Tree and an Edge References Class Ramsey Numbers Involving Induced Graphs 1 Introduction 2 Proofs of Main Results References Injective Edge Coloring of Power Graphs and Necklaces 1 Introduction 2 Main Results 3 Proof of Theorem 3 4 Proof of Theorem 4 References Total Coloring of Planar Graphs Without Some Adjacent Cycles 1 Introduction 2 Reducible Configurations 3 Discharging References Logic and Machine Learning Security on Ethereum: Ponzi Scheme Detection in Smart Contract 1 Introduction 2 Related Work 3 The Experimental Scheme 3.1 Feature Data Collection 3.2 Multi-granularity Data Construction Based on Opcode 3.3 Feature Construction of Frequency and Sequence 4 Model Construction 4.1 Frequency Model 4.2 Sequence Model and Account Model 5 Experimental Analysis 5.1 Analysis of Experimental Results 6 Summary References Learning Signed Network Embedding via Muti-attention Mechanism 1 Introduction 2 Preliminaries 2.1 Structural Balance Theory 2.2 Social Status Theory 3 Model Introduction 3.1 Select Appropriate Node Neighbors 3.2 Gather 1-layer Neighbor Information 3.3 Gather High Layer Neighbor Information 4 Experiment 4.1 Datasets 4.2 Baselines 4.3 Baseline Model Comparison Experiment 4.4 Superparametric Analysis 5 Conclusion References Three Algorithms for Converting Control Flow Statements from Python to XD-M 1 Introduction 2 Converting Algorithms of Complex Control Flow 2.1 The Algorithm of Converting continue Statement 2.2 The Algorithm of Converting break Statement 2.3 The Algorithm of Converting return Statement 2.4 Put Them All Together 3 Verification 3.1 Test Environment 3.2 Test Results 4 Conclusion References Hyperspectral Image Reconstruction for SD-CASSI Systems Based on Residual Attention Network 1 Introduction 2 Related Work 3 Proposed Method 3.1 Network Design 3.2 Loss Function 4 Experiment Setup 5 Result and Discussion 6 Conclusion References Author Index