Computing and Combinatorics: 28th International Conference, COCOON 2022, Shenzhen, China, October 22–24, 2022, Proceedings

Description

This book constitutes the proceedings of the 28th International Conference on Computing and Combinatorics, COCOON 2022, held in Shenzhen, China, in October 2022. The 39 full papers together with 12 short papers presented in this volume were carefully reviewed and selected from 101 submissions. The papers focus on subjects such as Algorithmica, Theoretical Computer Science, Journal of Combinatorial Optimization and others. Preface Organization Contents A Stochastic Non-monotone DR-Submodular Maximization Problem over a Convex Set 1 Introduction 2 Preliminaries 3 The SPIDER Frank-Wolfe Algorithm and Its Analysis 4 Conclusions References Flow Shop Scheduling Problems with Transportation Constraints Revisited 1 Introduction 2 PTAS for TF2|v=1,c1|Cmax 2.1 Construct an Instance of F3 Based on a Given Instance of TF2 2.2 Construct a Feasible Schedule of TF2 Based on a Known Schedule of F3 2.3 Construct a Feasible Schedule of F3 Based on a Known Schedule of TF2 2.4 PTAS for Problem TF2 3 PTAS for F2D|v=1,c1|Cmax 3.1 Construct an Instance of F3 Based on a Given Instance of F2D 3.2 Construct a Feasible Schedule of F2D Based on a Known Schedule of F3 3.3 Construct a Feasible Schedule of F3 Based on a Known Schedule of F2D 3.4 PTAS for Problem F2D 4 Conclusion References LotterySampling: A Randomized Algorithm for the Heavy Hitters and Top-k Problems in Data Streams 1 Introduction 2 Problem Formulation 2.1 Heavy Hitters 2.2 Top-k 3 The Algorithms 3.1 LotterySampling for Heavy Hitters 3.2 LotterySampling for Top-k 4 Comparison with Previous Work 4.1 Heavy Hitters 4.2 Top-k 5 Conclusion References Approximation Algorithms for the Min-Max Mixed Rural Postmen Cover Problem and Its Variants 1 Introduction 2 Notations 3 Min-Max Mixed Rural Postmen Cover Problem 3.1 Tour Split and Allocation 3.2 Find Tour 3.3 Algorithm Analysis 4 Min-Max Mixed Rural Postmen Walk Cover Problem 5 Min-Max Mixed Chinese Postmen Cover Problem 6 Conclusions References Large k-Gons in a 1.5D Terrain 1 Introduction 2 Case k=2: Diameter of the Terrain 3 Case k=3: Largest Perimeter Triangle 4 An FPTAS for *k 4.1 Preparation for Using Data Structures 4.2 A Largest Perimeter Triangle with Vertices on Three Intervals 5 Extension to Convex Polygons of at Most k Vertices 5.1 Perimeter Measure 5.2 Area Measure References Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-In Cascading Circuits 1 Background and Main Contributions 1.1 The Language Families kSDA and LOGkSDA 1.2 Nondeterministic Variants: k-sna's and aux-k-sna's 2 Basic Models of Computation 2.1 Auxiliary Storage Automata with Depth-Bounded Storage Tapes 2.2 Cascading Circuits with Semi-unbounded Fan-in Gates 3 Simulations Between Auxiliary SNAs and Cascading Circuit Families References Analysis of Approximate Sorting in I/O Model 1 Introduction 1.1 Background 1.2 Related Work 1.3 Measure of Approximate Results 1.4 Contribution 2 Preliminary and Problem Statement 2.1 I/O Model 2.2 New Metric: Errors 2.3 New Metric: ESP 2.4 Approximate Sorting in I/O Model 3 Theoretical Bound 3.1 Rate-Distortion Theory in I/O Model 3.2 Rate-Distortion Relationship for dee 3.3 Rate-Distortion Relationship for desp 4 Lower Bound 4.1 The Lower Bound of dee 4.2 The Lower Bound of desp 5 k-Pass Approximate Sorting Algorithm 5.1 Average ESP Metric of Algorithm 5.2 Average EE Metric of Algorithm 6 Future Work 7 Conclusion References Two Generalizations of Proper Coloring: Hardness and Approximability 1 Introduction 2 Preliminaries 3 Split Graphs and General Relations 4 Case of Two Colors 5 Perfect Graphs 6 Approximation Algorithms for Unit-Disk Graphs 6.1 Non-geometric Approach References Approximation Algorithms for Capacitated Assignment with Budget Constraints and Applications in Transportation Systems 1 The Problem 2 Related Work 2.1 Generalized Magician's Problem [Sect. 7]ch9alaei2014bayesian 3 Approximation Algorithm 3.1 A First Approximation Strategy 4 A Strategy Without Magicians for the Cases Without Assignment Costs 5 Applications in Real-Time Line Planning Problem (RLPP) 5.1 Numerical Experiments References On the Complexity of Minimum Maximal Acyclic Matchings 1 Introduction 2 Hardness Difference 3 NP-Completeness Result 4 Approximation Hardness 5 APX-Hardness for 4-Regular Graphs 6 Open Problems References Online Non-monotone DR-Submodular Maximization: 1/4 Approximation Ratio and Sublinear Regret 1 Introduction 2 Preliminaries 3 Problem Statement 4 Algorithm and Performance Analysis 5 Conclusion References Fair Division with Minimal Withheld Information in Social Networks 1 Introduction 2 Preliminaries 3 Attainability Problems 3.1 Lower Bounds on the Number of Hidden Items 3.2 Algorithms Finding the Sufficient Number of Hidden Items 4 Existence Problems 5 Verification Problems References Facility Location Games with Ordinal Preferences 1 Introduction 2 Preliminaries 3 Unknown Preferences 3.1 Maximum Cost 3.2 Total Cost 3.3 Minimum Utility 3.4 Total Utility 4 Unknown Locations 4.1 Minimizing the Maximum and Total Costs 4.2 Maximizing the Minimum and Total Utilities 5 Conclusion References Fully Dynamic k-Center Clustering with Outliers 1 Introduction 2 Preliminaries 3 Algorithms and Analysis 4 Conclusion References Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search 1 Introduction 2 Refutation of Graph Theory Conjectures 2.1 Graph Theory Conjectures 2.2 Algorithms Used to Refute Graph Conjectures 3 Algorithms 3.1 Monte Carlo Search 3.2 Nested Monte Carlo Search 3.3 Nested Rollout Policy Adaptation 3.4 Greedy Best First Search 4 Graph Generation 5 Experiments on Conjectures 5.1 Conjecture 1. AutoGraphiX 5.2 Conjecture 2. Aouchiche-Hansen 5.3 Conjecture 3. Collins 5.4 Conjecture 4. Graffiti 137 5.5 Comparison of Search Algorithms 6 Conclusion A Appendix - Algorithms B Appendix - Graphs References Online One-Sided Smooth Function Maximization 1 Introduction 1.1 Organizations 2 Preliminaries 3 The Approximation Algorithm and Its Analysis 3.1 Jump Start Meta Frank Wolfe Algorithm 3.2 Approximation Ratio 4 Conclusion References Revisiting Maximum Satisfiability and Related Problems in Data Streams 1 Introduction 2 Streaming Algorithms for Max-SAT 3 Streaming Algorithms for Min-SAT References Turing Machines with Two-Level Memory: A Deep Look into the Input/Output Complexity 1 Introduction 1.1 Related Works 2 Turing Machine with Two-Level Memory 2.1 Definition of Turing Machine with Two-Level Memory 2.2 TM-TLM v.s. Turing Machine 2.3 TM-TLM v.s. Block Transfer TM-TLM 2.4 IO Complexity v.s. Parameterized Complexity 3 The Random Access Turing Machine with Two-Level Memory 4 The Random Access Turing Machine with Blocking-IO 4.1 The Definition of Random Access Turing Machine with Blocking-IO 4.2 The External Access Trace Complexity 5 Conclusion References A Quantum Version of Pollard's Rho of Which Shor's Algorithm is a Particular Case 1 Introduction 2 A Characterization of Nontrivial Collisions 3 A Quantum Version of Pollard's Rho References Single Machine Scheduling with Rejection to Minimize the k-th Power of the Makespan 1 Introduction 1.1 Scheduling to Minimize the k-th Power of the Makespan 1.2 Scheduling with Rejection 2 Problem Formulation 3 Problem 1|split|(Cmax)k+JjRej 4 Problem 1||(Cmax)k+ JjRej 4.1 NP-Hardness Proof When k>1 4.2 Dynamic Programming Algorithms 4.3 Approximation Algorithms References Escape from the Room 1 Introduction 2 Preliminaries 3 Family Tree 4 Algorithm 5 Data Structure 6 Conclusion References Algorithms for Hard-Constraint Point Processes via Discretization 1 Introduction 1.1 Hard-Constraint Point Processes 1.2 Reduction to a Discrete Hard-Core Model 1.3 Approximation Algorithms via Canonical Discretization 1.4 Sampling via Random Perturbations 1.5 Discussion and Future Directions References Space Limited Graph Algorithms on Big Data 1 Introduction 2 Constructing a Maximal Matching 3 Kernelization for Edge Dominating Set 3.1 The First Kernelization Algorithm for P-EDS 3.2 A New Kernelization Algorithm for P-EDS 4 Conclusion and Final Remarks References Counting Cycles on Planar Graphs in Subexponential Time 1 Introduction 1.1 Overview 2 Self-Avoiding Walks and Partial Self-avoiding Walks 3 The Algorithm 3.1 Computing 69640972 CS(1, 2) 86418188 3.2 Computing 69640972 CD, S() 86418188 3.3 Computing 69640972 WG 86418188 4 Extensions References Semi-strict Chordal Digraphs 1 Introduction 2 Weakly Quasi-Transitive Semi-strict Chordal Digraphs 3 Locally Semicomplete Semi-strict Chordal Digraphs 4 Conclusion and Open Problems References Reallocation Problems with Minimum Completion Time 1 Introduction 2 Preliminaries 3 Algorithms for the Reallocation Problems 4 Intractability Results References The Bound Coverage Problem by Aligned Disks in L1 Metric 1 Introduction 2 Preliminaries 3 A Fully Polynomial Time Approximation Scheme 4 Conclusion References Facility Location Games with Group Externalities 1 Introduction 2 Preliminaries 3 Maximizing the Social Utility 3.1 Misreport only the Location 3.2 Misreport only the Preference 3.3 Misreport both the Location and Preference 4 Maximizing the Minimum Utility 4.1 Misreport only the Location 4.2 Misreport only the Preference 4.3 Misreport both the Location and Preference 5 Discussion and Future Work References Some New Results on Gallai Theorem and Perfect Matching for k-Uniform Hypergraphs 1 Introduction 1.1 Known Results 1.2 Our Results 2 Gallai Theorem for k-Uniform Hypergraphs 3 Perfect Matching on k-Uniform Hypertrees References Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 3 HRRC with Intersecting Regions 3.1 Positive Results 3.2 Negative Result 4 HRRC with Disjoint Regions 4.1 Positive Result 4.2 Negative Results References Customizable Hub Labeling: Properties and Algorithms 1 Introduction 1.1 Related Work 1.2 Contribution 2 Customizable Hub Labels 2.1 Definitions and Properties 2.2 Relationship to Customizable Contraction Hierarchies 3 Balanced Separators and Average Label Size 3.1 Lower Bounds 3.2 Approximation Algorithms 4 Customization Algorithms 4.1 Hierarchical CuHL 4.2 General CuHL 5 Conclusions and Future Work References Linear-Time Algorithm for Paired-Domination on Distance-Hereditary Graphs 1 Introduction 2 Algorithm for Distance-Hereditary Graphs 2.1 Decomposition Trees 2.2 The Algorithm 3 Correctness and Implementation Details 3.1 Essential Properties of k(v) 4 Conclusion and Future Work References Bounding the Number of Eulerian Tours in Undirected Graphs 1 Introduction 2 Pairings and Pairing Reductions 3 Edge-Distinct Eulerian Tours 3.1 Lower Bound 3.2 Upper Bound 4 Node-Distinct Eulerian Tours 4.1 Lower Bound Proof Scheme 4.2 Lower Bounding: Step 1 4.3 Lower Bounding: Step 2 4.4 Upper Bound References A Probabilistic Model Revealing Shortcomings in Lua's Hybrid Tables 1 Introduction 2 Hashmaps in Lua 2.1 Description of the Hashmap Algorithms 2.2 Settings and Analysis When There is No Deletion 2.3 General Analysis: An Unlikely Worst-Case Scenario 2.4 General Analysis: An Average-Case Scenario 3 Hybrid Tables in Lua 3.1 Settings for the Analysis 3.2 Rehashing into the Array-Part 3.3 Inserting Permutations in Lua Tables 3.4 Average Case for Insertion of Permutations 4 Conclusions and Final Remarks References A 4-Space Bounded Approximation Algorithm for Online Bin Packing Problem 1 Introduction 2 Preliminary 2.1 Our Contribution 2.2 Notation and Definitions 3 Algorithm A3 and Asymptotic Bound Analysis 3.1 Algorithm A3 3.2 Weight Function 3.3 Asymptotic Bound Analysis 3.4 Additive Term Analysis 4 Worst Case Analysis 5 Conclusion References Generalized Sweeping Line Spanners 1 Introduction 2 Preliminaries 3 Main Geometric Lemma 4 The Unconstrained Setting 5 The Constrained Setting 6 Polygonal Obstacles 7 Conclusion References Rooting Gene Trees via Phylogenetic Networks 1 Introduction 2 Basic Definitions 3 Supports of a Network 4 Unrooted Tree Reconciliation 5 Rooting a Gene Tree 5.1 Computing Weights of Edges of Unrooted Gene Trees 5.2 Time and Space Complexity of the Rooting Algorithm 6 Evaluation 6.1 Simulating Networks and Unrooted Gene Trees 6.2 Rooting Algorithm Results 7 Conclusions and Future Outlook References An Evolving Network Model from Clique Extension 1 Introduction 2 The Frustum Model 3 Cone Models 3.1 Small World Properties 3.2 Spectral Expansion 4 Conclusion and Future Directions References Online Semi-matching Problem with Two Heterogeneous Sensors in a Metric Space 1 Introduction 2 Preliminaries 3 The Optimal Online Algorithm 3.1 The Case 1 4 Discussion References Two-Stage BP Maximization Under p-matroid Constraint 1 Introduction 2 Preliminaries 3 Two-Stage BP Maximization 3.1 Algorithm for Two-Stage BP Maximization 3.2 Analysis of the Algorithm 4 Conclusion References The Hamiltonian Path Graph is Connected for Simple s,t Paths in Rectangular Grid Graphs 1 Introduction 2 Preliminaries 3 Square-Switches and the Zip Operation 3.1 P Almost Canonical 3.2 P Neither Canonical, nor Almost Canonical 4 Reconfiguration Algorithm 4.1 Reconfiguring P to P 4.2 Reconfiguring P to P' 4.3 Main Result 5 Conclusion and Open Problems References An O(n3)-Time Algorithm for the Min-Gap Unit-Length Job Scheduling Problem 1 Introduction 1.1 Related Work 1.2 Our Contributions 2 Algorithm 2.1 Notations Revisited and Two Assumptions 2.2 ALG's Ideas 2.3 The Detailed Dynamic Program Formulation 3 Analysis 3.1 Correctness Analysis 3.2 Running Time Analysis References Approximation Schemes for k-Facility Location 1 Introduction 1.1 Our Results 2 Preliminaries 3 The Sampling Step 4 The Construction Step 5 Conclusions References Improved Deterministic Algorithms for Non-monotone Submodular Maximization 1 Introduction 1.1 Our Contribution 1.2 Related Work 1.3 Organization 2 Preliminaries 3 Deterministic Approximation for Matroid Constraint 4 Deterministic Approximation for Knapsack Constraint 4.1 The Twin Greedy Algorithm 4.2 The Threshold Twin Greedy Algorithm 4.3 Obtaining Approximation-Preserving Feasible Solutions 4.4 A Tight Example for Twin Greedy 5 Conclusion and Future Work References Distributed Dominating Sets in Interval Graphs 1 Introduction 1.1 Previous Work 1.2 Our Contributions 2 Interval Graphs 2.1 MMDS: Interval Graphs 2.2 Correctness and Complexity 2.3 Lower Bound 2.4 MMCDS: Interval Graphs 3 Unit Interval Graph 3.1 MMDS: A 3 Factor Approximation Algorithm 3.2 MMDS: A PTAS 3.3 MMCDS: A 2 Factor Approximation Algorithm References Optimal Window Queries on Line Segments Using the Trapezoidal Search DAG 1 Introduction 2 Proposed TSD for General Input and the DFS Query 3 Expected Time of Vertical Segment-Queries 3.1 Windows Queries on Connected Planar Graphs References Rotation Distance for Rank Bounded Trees 1 Introduction 2 Preliminaries 3 Tree Permutations and Rotation 4 Computing Skew Rotation Distance via Tree Permutations 5 Rank Bounded Paths in the Rotation Graph References Hitting Geometric Objects Online via Points in Zd 1 Introduction 1.1 Related Work 1.2 Notation and Preliminaries 1.3 Our Contributions 2 Hypercubes in Rd 2.1 Lower Bound 2.2 Upper Bound 3 Balls in Rd 3.1 Lower Bound for Balls in Rd, for d