Combinatorial Optimization and Applications: 16th International Conference, COCOA 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II (Lecture Notes in Computer Science, 14462)

The two-volume set LNCS 14461 and LNCS 14462 constitutes the refereed proceedings of the 17th International Conference on Combinatorial Optimization and Applications, COCOA 2023, held in Hawaii, HI, USA, during December 15–17, 2023. The 73 full papers included in the proceedings were carefully reviewed and selected from 117 submissions. They were organized in topical sections as follows: Part I: Optimization in graphs; scheduling; set-related optimization; applied optimization and algorithm; Graph planer and others; Part II: Modeling and algorithms; complexity and approximation; combinatorics and computing; optimization and algorithms; extreme graph and others; machine learning, blockchain and others. Preface Organization Contents – Part II Contents – Part I Modeling and Algorithms Differentiable Discrete Optimization Using Dataless Neural Networks 1 Introduction 2 Statement of Problems 3 Related Work 4 Maximum Dissociation Set 5 k-Coloring 6 Maximum Cardinality d-Distance Matching 7 Conclusion References When Advertising Meets Assortment Planning: Joint Advertising and Assortment Optimization Under Multinomial Logit Model 1 Introduction 1.1 Summary of Contributions 2 Literature Review 3 Preliminaries and Problem Formulation 3.1 MNL Model 3.2 Joint Advertising and Assortment Optimization 4 Unconstrained JAAOP 5 Cardinality-Constrained JAAOP 5.1 g(x) as Linear Function 5.2 g(x) as a General Concave Function 6 Conclusion A Joint Assortment, Pricing, and Advertising Optimization A.1 Unconstrained Case A.2 Cardinality-Constrained Case B Sequential Joint Advertising and Assortment Optimization B.1 Heuristic Method C Numerical Study C.1 Compared Heuristics C.2 Performance Evaluation C.3 Effect of Budget on Expected Revenue D Omitted Proofs References Twin-Treewidth: A Single-Exponential Logic-Based Approach 1 Introduction 2 Preliminaries 3 Twin-Treewidth 3.1 Evaluation Information Function 3.2 Dynamic Programming 4 Final Remarks References Highway Preferential Attachment Models for Geographic Routing 1 Introduction 1.1 Kleinberg's Model 1.2 The Neighborhood Preferential Attachment Model 1.3 Our Results 2 Preliminaries 3 Kleinberg Highway 3.1 Results 4 Randomized Highway 4.1 Results 4.2 Greedy Routing Sketch 5 Windowed Neighborhood Preferential Attachment 5.1 Results 5.2 Efficient Construction 6 Future Work 7 Appendix 7.1 Experimental Analysis 7.2 Kleinberg Highway Proofs 7.3 Randomized Highway Proofs 7.4 Removing Local Contact Dependence 7.5 Randomized Highway Variant 7.6 Windowed NPA Proofs 7.7 Miscellaneous Proofs References Complexity and Approximation Restricted Holant Dichotomy on Domains 3 and 4 1 Introduction and Background 2 A Real Dichotomy for Holant*(f) on Domain 3 3 Holant*(f) Dichotomy for {0,1}-Valued f on Domain 4 3.1 Strategies 3.2 Interpolate Restricted Equalities References Earliest Deadline First Is a 2-Approximation for DARP with Time Windows 1 Introduction 2 Formalizing the Problem and Algorithm 2.1 The Earliest Deadline First (EDF) Algorithm 3 Our Results 4 Concluding Remarks References Improved Approximation for Broadcasting in k-Path Graphs 1 Introduction 2 k-Path Graphs 3 Broadcasting from a Junction Vertex 3.1 Complexity Analysis 3.2 The Approximation Ratio 4 Broadcasting from an Internal Vertex 4.1 Complexity Analysis 4.2 The Approximation Ratio 5 Conclusion and Future Work References The Fine-Grained Complexity of Approximately Counting Proper Connected Colorings (Extended Abstract) 1 Introduction 2 Applications of k-Proper Connected w-Colorings to the Frequency Assignment Problem 3 Preliminaries 3.1 Graph Theoretic Notions and Terminology 3.2 Counting Complexity 3.3 Approximate Counting 3.4 Exponential Time Hypothesis (ETH) and Counting Exponential Time Hypothesis (#ETH) 3.5 Variants of Not-All-Equal SAT 4 Exactly and Approximately Counting Proper Connected Colorings 5 Concluding Remarks References Combinatorics and Computing Strong Edge Coloring of Subquartic Graphs 1 Introduction 2 Notations 3 Proof of Theorem 7 4 Further Considered Problems References Two Multicolor Ramsey Numbers Involving Bipartite Graphs 1 Introduction 2 Proofs of Main Results References Mechanism Design for Time-Varying Value Tasks in High-Load Edge Computing Markets 1 Introduction 2 System Model and Problem Statement 2.1 Resource Model of the System 2.2 Utility Model of the System 2.3 Optimization Goals for Maximizing Social Welfare 3 The Greedy Auction Mechanism 3.1 Resource Allocation Strategy 3.2 GMPO-W Winner Decision 3.3 GMPO-P Price Determination Mechanism 4 Evaluation Results 4.1 Experimental Settings 4.2 Numerical Results 5 Conclusion References Computing Random r-Orthogonal Latin Squares 1 Introduction 2 Preliminaries 3 Completing Orthogonal Latin Rectangles 4 Computing Self-orthogonal Latin Rectangles References Optimization and Algorithms A Two-Stage Seeds Algorithm for Competitive Influence Maximization Considering User Demand 1 Introduction 2 Propagation Model and Algorithm 2.1 Propagation Model 2.2 Problem Formulation 2.3 Algorithm Consider Dual Influence Assessment Based on Community Structure 3 Experiment 3.1 Dataset 3.2 Experiment Design 3.3 Experiment Results 4 Conclusion References Practical Attribute-Based Multi-keyword Search Scheme with Sensitive Information Hiding for Cloud Storage Systems 1 Introduction 2 Problem Formulation and Preliminaries 2.1 System Model 2.2 Threats Model and Design Goals 2.3 Preliminaries 3 The Proposed ABMKS-SIH Scheme 4 Security Analysis of ABMKS-SIH 4.1 Security Model 4.2 Security Proofs 5 Comparison and Evaluation 6 Conclusion References Testing Higher-Order Clusterability on Graphs 1 Introduction 1.1 Motivation 1.2 Related Work 1.3 Contributions 1.4 Organization of the Paper 2 Preliminary and Problem Statement 2.1 Testing Clusterability on Bounded-Degree Graphs 2.2 Testing Higher-Order Clusterability on Bounded-Degree Graphs 3 Analysis of Compatibility and Lower Bound 3.1 Compatibility with Framework of Testing Clusterability 3.2 Compatibility of High-Dimension (k,in,out)-Cluster 3.3 Lower Bound of Testing Higher-Order Clusterability 4 Algorithm of Testing Triangle-Based Clusterability 4.1 Design of Triangle-Based k-Cluster Tester 4.2 Correctness and Running Time Analysis 5 Summary and Future Work References The 2-Mixed-Center Color Spanning Problem 1 Introduction 2 Literature Review 3 Preliminary 4 The Exact Algorithm for 2-MCCSP 5 A 2-Approximation Algorithm for 2-MCCSP 6 Conclusions References A Dynamic Parameter Adaptive Path Planning Algorithm 1 Introduction 2 Two Reinforcement Learning Algorithms 2.1 Q-Learning Algorithm 2.2 Sarsa Algorithm 3 DPARL Algorithm 4 Experimental Setup and Experimental Results 4.1 Description of the Path Planning Problem 4.2 Modeling and Parameter Settings for the Path Planning Problem 4.3 Experimental Results and Analysis 5 Conclusions References On the Mating Between a Polygonal Curve and a Convex Polygon 1 Introduction 2 Preliminaries 3 A Necessary and Sufficient Condition 4 The Algorithms 4.1 The Dynamic-Programming Algorithm 4.2 The Greedy Algorithm 4.3 Characterizing Polygonal Curves Matable with Some Convex Polygon 5 Conclusion References A Faster Parameterized Algorithm for Bipartite 1-Sided Vertex Explosion 1 Introduction 2 Terminology and Notations 3 Linear Kernel 4 Efficient Branching Rules 5 A Whole Parameterized Algorithm 6 Conclusion and Further Work References Multi-winner Approval Voting with Grouped Voters 1 Introduction 2 Preliminaries 2.1 Approval Voting Rules 2.2 Axioms 2.3 The Models 3 Large/Small Group Benefited Representation 4 Parameterized Complexity 5 Concluding Remarks References EFX Allocation to Chores over Small Graph 1 Introduction 2 Preliminaries 3 Warm-Up: EFX Allocation for Three Agents and Star Structured Agents 4 An EFX Allocation for LFA 4.1 At Least Three Special Agents 4.2 Two Special Agents 4.3 At Most One Special Agent 5 Discussion and Conclusion References Extreme Graph and Others Zero-Visibility Cops and Robber Game on Cage Graph 1 Introduction 2 Preliminaries and Basic Definitions 2.1 Graph Theory Notion 2.2 Cops and Robber 3 The Monotonic Zero-Visibility Cop Number of Cage Graph 3.1 Lower Bounds of Cop Number 3.2 Cop Number of Cage Graph 4 Algorithm for the Monotonic Zero-Visibility Strategy of Cage 5 Conclusion and Further Discussion References Online Facility Assignment for General Layout of Servers on a Line 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Online Facility Assignment Problem 2.2 Online Facility Assignment Problem on a Line 2.3 Notations and Terminologies 2.4 Technical Lemmas 3 ``Hybrid'' Algorithm 4 An Optimal MPFS Algorithm for OFAL 4.1 A New Algorithm: Policy Transition at Critical Point 4.2 An Upper Bound on the Competitive Ratio of PTCP 4.3 Comparisons with Other Algorithms 5 A Lower Bound on the Competitive Ratio of MPFS 6 Concluding Remarks and Open Questions References Guarding Precise and Imprecise Polyhedral Terrains with Segments 1 Introduction 2 Preliminaries 3 Polynomial-Time Algorithms on Guarding Polyhedral Terrains with a Segment 3.1 A Linear Time Algorithm for 1.5D Terrains 3.2 An Almost Cubic Time Algorithm for 2.5D Terrains 4 A Polynomial-Time Algorithm on Guarding 1.5D Polyhedral Terrains with Two Horizontal Segments 5 Guarding a 1.5D Imprecise Terrain 6 Concluding Remarks References The Bag-Based Search: A Meta-Algorithm to Construct Tractable Logical Circuits for Graphs Based on Tree Decomposition 1 Introduction 2 Preliminary 2.1 Subgraphs and Their Boolean Representation 2.2 Tractable Logical Circuits (TLCs) 2.3 Tree Decompositions (TDs) 3 The Bag-Based Search (BBS) 3.1 S-States and S-Updates 3.2 M-States and M-Updates 3.3 The Bag-Based Search (BBS) 3.4 Tractableness of Generated Circuits by BBS 4 BBS Examples 5 Experiments 5.1 Experimental Setting 5.2 Experimental Results 6 Conclusion References On Problems Related to Absent Subsequences 1 Introduction 2 Absent Subsequence Automaton 3 Shortest Absent Subsequences 4 Minimal Absent Subsequences 5 Distinguishing Words 6 Conclusion References Some Combinatorial Algorithms on the Dominating Number of Anti-rank k Hypergraphs 1 Introduction 1.1 Related Works 1.2 Our Results 2 The Anti-rank 3 Hypergraphs 3 The Anti-rank 4 Hypergraphs 4 The Anti-rank k Hypergraphs 5 The Random Hypergraph Model References Parameterized and Exact-Exponential Algorithms for the Read-Once Integer Refutation Problem in UTVPI Constraints 1 Introduction 2 Statement of Problem 2.1 Constraint System 2.2 Refutation System 2.3 Read-Once Refutations 3 Motivation and Related Work 4 A Fixed-Parameter Algorithm 5 Kernelization Lower Bounds 6 Lower Bounds on Exponential Algorithms 7 An Exact Exponential Algorithm 8 Conclusion References Critical (P5,dart)-Free Graphs 1 Introduction 2 Preliminaries 3 Structure Around 5-Hole 4 The Proof of Theorem 4 5 Complete Characterization for k {5,6,7} 6 Conclusion References Graph Clustering Through Users' Properties and Social Influence 1 Introduction 2 Problem Statement 3 Similarity Measure 3.1 Mutual Influence 3.2 Self Influence 3.3 The Combination of Different Parts 4 Clustering with Influence Analysis Algorithm 5 Experiment and Performance 6 Conclusion References Machine Learning, Blockchain and Others Incorporating Neural Point Process-Based Temporal Feature for Rumor Detection 1 Introduction 2 Related Work 2.1 Rumor Detection Methods with Multiple Features 2.2 Deep Learning Approaches for Point Process 3 Preliminaries 3.1 Problem Statement 3.2 Neural Temporal Point Process 3.3 Temporal Pattern in Rumor Propagation 4 Model 4.1 Temporal Feature Construction 4.2 Rumor Detection Module 5 Experiments 5.1 Settings and Datasets 5.2 Experimental Results 6 Conclusions References Improving Contraction Hierarchies by Combining with All-Pairs Shortest Paths Problem Algorithms 1 Introduction 2 Preliminaries 2.1 Contraction Hierarchies 2.2 All-Pairs Shortest Paths Problem 3 CH-APSP 3.1 Preprocessing 3.2 Query 4 Experiments and Analysis 4.1 Impact of APSP Algorithms and Remaining Nodes(M) on Preprocessing 4.2 Impact of M on Query 5 Conclusions and Future Work References Information Theory of Blockchain Systems 1 Introduction 2 Model Description 3 Maximum Entropy in Blockchain Systems 3.1 Entropy Function 3.2 Prior Information 3.3 The Maximum Entropy Principle 4 Numerical Experiments 5 Concluding Remarks References Machine Learning with Low-Resource Data from Psychiatric Clinics 1 Introduction 2 Data Augmentation 3 Transfer Learning 4 Few-Shot/Zero-Shot Learning 5 Active Learning 6 Self-supervised Learning 7 Multi-task Learning 8 Conclusion References Single Image Dehazing Based on Dynamic Convolution and Transformer 1 Introduction 2 Our Method 2.1 T-DRC Module 2.2 Improved Dynamic Residual Module 2.3 Dual Attention Module 2.4 Transformer Module 2.5 Gated Fusion Block 2.6 MixUp Module 2.7 Loss Function 3 Experiments 3.1 Datasets and Evaluation Indicators 3.2 Experimental Setup 3.3 Synthetic Haze Image Dataset Experiment 3.4 Real Haze Image Dataset Experiment 3.5 Ablation Experiments 4 Conclusion References Reinforcement Learning for Combating Cyberbullying in Online Social Networks 1 Introduction 2 Background and Related Work 3 Problems Formulation 3.1 Diffusion Model 3.2 Problem Statement 4 Methodology 4.1 Initial Node Embedding 4.2 Dynamic Interactive Graph Neural Network 4.3 Reinforcement Learning 5 Experiments 5.1 Experiment Setup 5.2 Results 6 Conclusions References Author Index