Computing and Combinatorics: 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II (Lecture Notes in Computer Science)

This two volume set volume LNCS 14422-14423 constitutes the refereed proceedings of the 29th International Conference, COCOON 2023, held in Hawaii, HI, USA, during December 2023. The 60 full papers were carefully reviewed and selected from 146 submissions. They are organized in the following topical sections: Part I : Combinatorics and Algorithms; Algorithmic Solution in Applications; and Algorithm in Networks. Part II: Complexity and Approximation; Graph Algorithms; and Applied Algorithms. Preface Organization Contents – Part II Contents – Part I Combinatorics and Algorithms Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher 1 Introduction 2 Overviews of Previous Results and Our Ideas 3 Preliminaries 4 Proof Sketch of Quantum Query Lower Bounds 5 Concluding Remarks References Extended Formulations via Decision Diagrams 1 Introduction 2 Related Work 3 Preliminaries 4 NZDDs for Linear Constraints with Binary Coefficients 5 Extensions to Integer Coefficients 6 Construction of NZDDs 7 Experiments 7.1 Mixed Integer Programming on Synthetic Datasets 7.2 1-norm Soft Margin Optimization on Real Data Sets 8 Conclusion References Greedy Gray Codes for Dyck Words and Ballot Sequences 1 Introduction 2 Gray Codes for Dyck Words and Fixed-Weight Dyck Prefixes 3 Proof of Theorem 1 4 Gray Codes for Ballot Sequences 5 Final Remarks References Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication 1 Introduction 2 Preliminaries 3 Simplification and Efficiently-Verifiable SUSPs 4 Simplifiable SUSPs Generate Infinite Families 5 New Lowers Bounds on Maximum SUSP Size 6 Conclusions References (min,+) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences 1 Introduction 2 Preliminaries 3 (min,+) Matrix Product 4 (min,+) Convolution References A Sub-quadratic Time Algorithm for Computing the Beacon Kernel of Simple Polygons 1 Introduction 1.1 Previous Works 2 Preliminaries 3 The Discrete Beacon Kernel Problem 4 The Beacon Kernel Problem 4.1 The Split Decomposition Tree of P 4.2 Computing Candidate Kernel Points 4.3 Building the Beacon Kernel References An Approach to Agent Path Planning Under Temporal Logic Constraints 1 Introduction 2 Preliminaries 3 LCAP2 3.1 Property Extraction for Path Planning in Gridworld 3.2 Formulating Multi-Objective Optimization Problem 3.3 Reward Design Method 4 Experiments 5 Convergence Theorem 6 Conclusion References The Heterogeneous Rooted Tree Cover Problem 1 Introduction 2 Terminologies and Fundamental Lemmas 3 An Approximation Algorithm with Constant Approximation Ratio 4 An Approximation Algorithm with Lower Time Complexity 5 Conclusion and Further Work References The Hardness of Optimization Problems on the Weighted Massively Parallel Computation Model 1 Introduction 1.1 Description of the Research Problems in This Paper 1.2 Summary of Results and Paper Organization 1.3 Denotations 2 The Data Redistribution Problem Series 3 The Problem Series of Data Allocation Problem 3.1 The Splitter-Graph 3.2 FPT Algorithm of DAP-TOTAL and DAP-BTNK 3.3 W[1]-Completeness of DAP-MSR and DAP-SSR 4 Future Works 5 Conclusion References The Regularized Submodular Maximization via the Lyapunov Method 1 Introduction 1.1 Lyapunov Function Approach 1.2 Related Work 1.3 Our Contribution 1.4 Organization 2 Preliminaries 3 Lyapunov Method – Continuous-Time Phase 4 Conclusion A Technical Lemmata B Discrete-Time Phase for RegularizedNSM C The Lyapunov Method for RegularizedMSM D Missing Proofs in Section3 References Topological Network-Control Games 1 Introduction, Preliminary Definitions and Results 1.1 Statement of the Problem 1.2 Preliminaries and Basic Results 1.3 Related Work and Our Contribution 2 Games on Paths, Cycles, and Caterpillars 3 Parity Vs the Number of Claimed Vertices 4 Topological Network-Control Games on Path1 Path2 5 PSPACE-Completeness References Lower Bounds of Functions on Finite Abelian Groups 1 Introduction 2 Preliminaries 2.1 Fourier Analysis on Groups 2.2 Sparse Fourier Sum of Squares on Finite Abelian Groups 3 Main Results 3.1 Lower Bounds by FSOS 3.2 FSOS with Error 3.3 Computation of Lower Bounds 3.4 Rounding 4 Numerical Experiments 4.1 Upper Bounds of MAX-2SAT Problems 4.2 Rounding Techniques 4.3 Lower Bounds of Random Functions References A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering 1 Introduction 2 Preliminaries 3 Fat-Head Crown Decomposition 4 The Algorithms 4.1 Simple Rules 4.2 Adjustments Based on a Triangle Packing 4.3 A Reduction Based on Fat-Head Crown Decomposition 5 Analysis Based on Discharging 5.1 The Analysis 6 Conclusion References Random Shortening of Linear Codes and Applications 1 Introduction 1.1 Previous Work 1.2 Notation and Definitions 1.3 Main Results 1.4 Technique Overview 2 Estimation on Low-Biased Codewords 3 Proof of the Main Theorems References Algorithms for Full-View Coverage of Targets with Group Set Cover 1 Introduction 2 Preliminaries 3 Problem Formulation 3.1 Group Set Cover with Time Segmented Cumulative Full-View Target Coverage (TSC-FTC) 3.2 Group Set Cover with Cumulative Maximum Full-View Target Coverage Time Window (FTC-TW) 4 Conclusion References Improved Bounds for the Binary Paint Shop Problem 1 Introduction 2 Lower Bounds 3 Small Improvement of the Upper Bound 4 Recursive Star Greedy Heuristics 5 Concentration Result for the Optimal Number of Color Changes References Algorithmic Solution in Applications Fitch Graph Completion 1 Introduction 2 Preliminaries 3 Fitch Graphs and Fitch-Satisfiability 4 Recognition Algorithm and Computational Complexity 5 Concluding Remarks References Deterministic Primal-Dual Algorithms for Online k-Way Matching with Delays 1 Introduction 2 Preliminaries 2.1 Minimum-Cost Perfect k-Way Matching with Delays 2.2 H-Metric 2.3 Properties of H-Metric 3 k-MPMD on H-Metric Space 3.1 Linear Programming Relaxation 3.2 Greedy Dual for k-MPMD (GD-k) 3.3 Competitive Ratio of GD-k 4 Lower Bound of GD-k for a Diameter on a Line References Diversity and Freshness-Aware Regret Minimizing Set Queries 1 Introduction 2 Preliminaries 2.1 Basic Notions 2.2 Problem Definition 2.3 Hardness 2.4 Background 3 Algorithm and Algorithm Analysis 3.1 Algorithm for MS 3.2 Algorithms for MSDF 4 Conclusion References A Modified EXP3 in Adversarial Bandits with Multi-user Delayed Feedback 1 Introduction 2 Problem Formulation 3 Algorithm 4 Regret Analysis 5 Related Work 6 Conclusion A Appendix: Proof of Lemma 3 References Cabbage Can't Always Be Transformed into Turnip: Decision Algorithms for Sorting by Symmetric Reversals 1 Introduction 2 Preliminaries 3 An O(n2) Algorithm for SSR with Duplication Number 2 4 An O(n2) Decision Algorithm for the General Case 5 Concluding Remarks References k-Median/Means with Outliers Revisited: A Simple Fpt Approximation 1 Introduction 2 A Coreset-Based Fpt Approximation 3 Conclusion References A Cost-Sharing Scheme for the k-Product Facility Location Game with Penalties 1 Introduction 2 Preliminary Algorithm 3 The Cost-Sharing Scheme for the k-PFLGPN 3.1 Algorithm for the k-PFLGPN 3.2 Analysis of Algorithm 2 4 Conclusions References Algorithm in Networks Maximizing Diversity and Persuasiveness of Opinion Articles in Social Networks 1 Introduction 2 Related Work 3 The Model 4 Problem Formulation 5 The Algorithm 6 Experiments Settings and Results 7 Conclusion References Stochastic Model for Rumor Blocking Problem in Social Networks Under Rumor Source Uncertainty 1 Introduction 1.1 Related Works 2 Problem Formulation 2.1 Rumor Spreading Model 2.2 Stochastic Rumor Blocking Problem 2.3 Strategies for Choosing ``Protector'' 3 Properties of Stochastic Rumor Blocking 3.1 Hardness Results 3.2 Modularity of Objective Function 4 Algorithm 4.1 CRIS Sampling 4.2 Randomized Greedy Algorithm 5 Conclusions References Algorithms for Shortest Path Tour Problem in Large-Scale Road Network 1 Introduction 2 Algorithm 2.1 Stage Dijkstra 2.2 Global Dijkstra 2.3 Complexity Analysis 3 Correctness Proof 3.1 Correctness Proof for Stage Dijkstra 3.2 Correctness Proof for Global Dijkstra 4 Experiments 4.1 Baseline Methods 4.2 Dataset 4.3 Configurations and Metric 4.4 Results 5 Conclusion References Solving Systems of Linear Equations Through Zero Forcing Set 1 Introduction 2 Preliminaries 3 Solving Ax=b Through Zero Forcing Set 3.1 Core Matrix 3.2 The Algorithm 4 Lights Out Game on a Grid References Profit Maximization for Competitive Influence Spread in Social Networks 1 Introduction 2 Related Work 3 Diffusion Model and Problem Definition 3.1 The Diffusion Model 3.2 Problem Formulation 4 Solution for PMPCIS 4.1 Properties for Objective Function f 4.2 Proposed Algorithm 4.3 Approximation Performance Analysis 5 Conclusion References Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing 1 Introduction 1.1 Our Contributions 2 Preliminaries 2.1 Definitions 2.2 Assumptions 3 Lower Bounds 4 Review of the Previous Algorithms 4.1 The Cycle-Partition Algorithm 4.2 The Tree-Partition Algorithm 5 An Improvement for Splittable MCVRP 6 An Improvement for Unsplittable MCVRP 7 An Improvement for k-MCVRP with Fixed Capacity 8 Conclusion References On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes 1 Introduction 1.1 Background and Results 2 Inverse Ackermann Functions 3 Upper Bound 4 Depth Lower Bound 5 Superconcentrator-induced Codes 6 Conclusion References Approval-Based Participatory Budgeting with Donations 1 Introduction 2 Preliminaries 3 Normal PB Rules 4 Sequential Rules 5 Pareto Rules 6 Conclusion References Author Index