Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings (Theoretical Computer Science and General Issues)

Preface
Organization
Contents
Routing Among Convex Polygonal Obstacles in the Plane
1 Introduction
2 A Few Structures
2.1 Sketch of P
2.2 Routing Path and Its Stretch
2.3 Geodesic Cones
2.4 Piece
3 Algorithm
References
Target Coverage with Minimum Number of Camera Sensors
1 Introduction
1.1 Related Work
1.2 Our Results
1.3 Organization
2 Integer Linear Programs
2.1 Camera Sensor Group
2.2 Integer Linear Programming Formulation
3 LP-Rounding Algorithm via Transformation to the Shortest Matching-Path Problem
3.1 The Construction
3.2 Linear Programming for Shortest Matching-Path Problem
4 Numerical Experiments
4.1 Solution Quality in Comparison
4.2 Runtime Comparison
5 Conclusion
References
Two-Stage Submodular Maximization Under Curvature
1 Introduction
2 Two-Stage Submodular Maximization
2.1 Algorithm for Two-Stage Submodular Maximization
2.2 Analysis of the Algorithm
3 Conclusion
References
An Improved Approximation Algorithm for Capacitated Correlation Clustering Problem
1 Introduction
2 Preliminaries
3 Algorithm and Analysis
3.1 Iterative Clustering Algorithm
3.2 Theoretical Analysis
4 Numerical Experiments
4.1 Datasets
4.2 Experimental Setup and Results
5 Conclusions
References
The Selection of COVID-19 Epidemic Prevention and Control Programs Based on Group Decision Making
1 Introduction
2 Theoretical Basis
3 General Process of Group Decision Making in Epidemic Prevention and Control Programs
4 The Realization of Group Decision Making for NAT Solutions in Epidemic Prevention and Control
5 Conclusions
References
Which Option Is a Better Way to Improve Transfer Learning Performance?
1 Introduction
2 Related Works
3 Problem Formulation
4 Collecting Instances vs. Collecting Attributes
5 Whether to Collaboration
6 Collection vs. Collaboration
7 Conclusion and Future Work
References
On Maximizing the Difference Between an Approximately Submodular Function and a Linear Function Subject to a Matroid Constraint
1 Introduction
2 Preliminaries
3 A Bicriteria Algorithm
4 An Extended Bicriteria Algorithm for Hiigh Volume Data
5 Conclusion
References
On Various Open-End Bin Packing Game
1 Introduction
2 Definitions and Terminologies
3 General Open-End Bin Packing Game
3.1 Existence of Nash Equilibrium in the General Open-End Bin Packing Game
3.2 The Upper Bound of Price of Anarchy
3.3 The Lower Bound of Price of Anarchy
4 Minimum Open-End Bin Packing Game
4.1 Existence of Nash Equilibrium in Minimum Open-End Bin Packing Game
4.2 The Upper Bound of Price of Anarchy
4.3 The Lower Bound of Price of Anarchy
5 Open-End Bin Packing Game with Conflict
5.1 Existence of Nash Equilibrium
5.2 Open-End Bin Packing Game with a Complete Multipartite Conflict Graph
5.3 The Upper Bound of the Price of Anarchy
5.4 Open-End Bin Packing with a Simple Conflict Graph
6 Conclusion
References
A Linear-Time Streaming Algorithm for Cardinality-Constrained Maximizing Monotone Non-submodular Set Functions
1 Introduction
2 Preliminaries
3 The Single-Pass Deterministic Algorithm
4 Discussion
References
Approximation Algorithms for Two Parallel Dedicated Machine Scheduling with Conflict Constraints
1 Introduction
2 Problem Statement
3 The SWC Problem with a Fixed Sequence
3.1 A 95-Approximation Algorithm
3.2 Tight Analysis of Approx1 for Two Subproblems
3.3 An Improved Algorithm for Subproblem 2
4 The SWC Problem Without Any Fixed Sequence
5 Conclusions
References
Computing the One-Visibility Cop-Win Strategies for Trees
1 Introduction
2 Structures of Trees by Copnumbers
3 Computing Copnumbers and Roadmaps
4 Computing Optimal Cop-Win Strategies
References
Complexity and Approximation Results on the Shared Transportation Problem
1 Introduction
2 Problems Description
2.1 Notation
2.2 Objective Functions
3 Polynomial Cases
4 Computational Hardness
4.1 Each Color Induces a Path of Bounded Length
4.2 In Bipartite and Planar Graphs
4.3 In Paths
5 Approximation Results
6 Lower Bounds for Exact Algorithms
7 Conclusion
References
The Complexity of Finding Optimal Subgraphs to Represent Spatial Correlation
1 Introduction
1.1 Our Contribution
1.2 Paper Outline
2 Background
2.1 Notation and Definitions
2.2 The Optimisation Problem
2.3 Why Common Graph Algorithm Techniques Fail
3 Hardness on Planar Graphs
4 Simplifications of the Problem
4.1 Minimising Neighbourhood Discrepancy
4.2 Ideal and Near-Ideal Subgraphs
5 Parameterised Results
5.1 An Exact XP Algorithm Parameterised by Treewidth and Maximum Degree
5.2 Parameterisation by k in Low Degree Graphs
6 Discussion and Conclusions
References
New Approximation Algorithms for the Rooted Budgeted Cycle Cover Problem
1 Introduction
1.1 Related Work
1.2 Our Results
1.3 More Related Work
2 Single Depot Budgeted Cycle Cover
2.1 Layering of Vertices and the Algorithm
2.2 Analysis
3 Multi-depot Budgeted Cycle Cover
3.1 The Algorithm
3.2 Analysis
4 Experiments
5 Conclusions
References
Evolutionary Equilibrium Analysis for Decision on Block Size in Blockchain Systems
1 Introduction
2 System Model and and Mining Pool's Expected Reward
3 Evolutionary Game Model for Decision on Block Size
3.1 Analysis Scheme
3.2 A Case Study of Two Mining Pools
4 Numerical Experiments and Conclusions
4.1 Numerical Experiments
4.2 Conclusion
References
Efficient Algorithms for Scheduling Parallel Jobs with Interval Constraints in Clouds
1 Introduction
2 Polyhedron and LP-Based Algorithm for MPI-CJ
2.1 Polyhedron of MPI-CJ
2.2 LP-Based Algorithm for MPI-CJ
2.3 Performance Comparison of Our Algorithm with EDF and LLF
3 Conclusion
References
Two-Stage Stochastic Max-Weight Independent Set Problems
1 Introduction
2 Preliminaries
3 The Two-Stage Maximum-Weight Independent Set Problem
3.1 Main Result and Analysis for Independent Set Problems
3.2 A 12-Approximation Algorithm for the Discrete Two-Stage Stochastic Maximum-Weight Matroid Independent Set Problem
References
Routing and Scheduling Problems with Two Agents on a Line-Shaped Network
1 Introduction
2 Problem Without Release Time
3 Problem with Release Time
3.1 Special Case
3.2 General Case
4 Conclusions
References
The Price of Anarchy of Generic Valid Utility Systems
1 Introduction
2 Preliminaries
2.1 Game Theory
2.2 Submodular Function
3 Generic Valid Utility Systems
3.1 Definitions and Properties
3.2 PoA of a Generic Basic Utility System
3.3 Mechanism of Generic Valid Utility System
References
Single Machine Scheduling with Rejection and Generalized Parameters
1 Introduction
1.1 Scheduling with Rejection
1.2 Scheduling with Generalized Due Dates
1.3 Scheduling with Rejection and Generalized Due Dates
2 Problem Formulation
3 Scheduling with Generalized Release Dates
3.1 NP-Hardness Proof
3.2 Dynamic Programming Algorithm
3.3 Approximation Algorithms
4 Scheduling with Generalized Processing Times
5 Scheduling with Generalized Rejection Cost
6 Conclusions and Future Research
References
Approximation Algorithm and Hardness Results for Defensive Domination in Graphs
1 Introduction
2 Preliminaries
3 NP-Completeness Result for Bipartite Graphs
4 Lower Bounds on Approximation Ratio
5 Approximation Algorithm
6 APX-Completeness
7 Defensive Domination Complete Bipartite Graphs
8 Conclusion
References
An Improved Physical ZKP for Nonogram
1 Introduction
1.1 Zero-Knowledge Proof
1.2 Related Work
1.3 Our Contribution
2 Preliminaries
2.1 Cards
2.2 Random Cut
2.3 Pile-Shifting Shuffle
2.4 Copy Protocol
2.5 Chosen Cut Protocol
3 Main Protocol
3.1 Phase 1: Counting Black Cells
3.2 Phase 2: Removing White Cells
3.3 Phase 3: Verifying Order of Blocks
3.4 Optimization
4 Proof of Security
5 Future Work
References
Finding All Leftmost Separators of Size k
1 Introduction
1.1 Notation
1.2 Our Contributions
2 Finding the Leftmost Minimum Size (X, Y, k)G-Separator
3 Finding All Minimal Leftmost (X, Y, k)-Separators
4 Application to Treewidth Approximation
4.1 Our Improvement
References
Maximize the Probability of Union-Influenced in Social Networks
1 Introduction
2 Related Work
3 Problems Formulation
4 The UIS-Based Algorithms Designs
5 Experiments
6 Conclusions
References
A Novel Algorithm for Max Sat Calling MOCE to Order
1 Introduction
2 The Greedy Order MOCE (GO-MOCE)
2.1 The Concept of Gain and Its Usage in GO-MOCE
2.2 Efficient Instance Representation and Residualization
2.3 Efficient Maintenance and Update of Gains
2.4 Pseudocode
3 Time Complexity
3.1 A Linearithmic Time Complexity Implementation
3.2 A Linear Time Complexity Implementation
4 Performance Analysis
5 Improving a State-of-the-Art Solver Using GO-MOCE
6 Conclusion
References
The Smallest Number of Vertices in a 2-Arc-Strong Digraph Without Pair of Arc-Disjoint In- and Out-Branchings
1 Introduction
2 Proofs Outline
2.1 Theorem 2
2.2 Theorem 3
2.3 Theorem 4
3 Preliminaries and Useful Lemmas
4 Good Pairs in Digraphs of Order 7
5 Good Pairs in Digraphs of Order 8
6 Good Pairs in Digraphs of Order 9
References
Generalized Self-profit Maximization in Attribute Networks
1 Introduction
2 Problem Formulation
2.1 Attribute Networks
2.2 Profit Complementary Independent Cascade Model and Diffusion Dynamics
2.3 Problem Statements
3 R-GSMA Algorithm
4 Experiment
4.1 Experimental Settings
4.2 Experimental Results
5 Conclusion and Future Works
References
Parameterized Complexity Classes Defined by Threshold Circuits: Using Sorting Networks to Show Collapses with W-hierarchy Classes
1 Introduction
2 Satisfiability of Threshold Circuits
2.1 Preliminaries
2.2 The Th-hierarchy
3 W-hierarchy Versus Th-hierarchy
4 On the Classes Th[t], Th[SAT], and W[SAT]
4.1 AKS Sorting Networks
4.2 Th[t] W[SAT]
References
Maximization of Monotone Non-submodular Functions with a Knapsack Constraint over the Integer Lattice
1 Introduction
1.1 Preliminaries
1.2 Problem Formulation
1.3 Organization
2 Algorithms
3 Conclusions
References
Sublinear-Time Reductions for Big Data Computing
1 Introduction
1.1 Our Results
2 Preliminaries
3 Pseudo-sublinear-Time Reduction
4 Pseudo-polylog-Time Reduction
5 Approximation Preserving Pseudo-sublinear-Time Reduction
6 Complete Problems in PPL
7 Conclusion
References
Capacitated Partial Inverse Maximum Spanning Tree Under the Weighted l-norm
1 Introduction
2 Main Results
2.1 Algorithm for the Decision Version of CPIMST
2.2 Algorithm for CPIMST Under the Un-Weighted l-norm
2.3 CPIMST Under the Weighted l-norm
3 Conclusion
References
Approximation Algorithms for Some Min-Max and Minimum Stacker Crane Cover Problems
1 Introduction
2 Preliminaries
3 Min-Max Stacker Crane (Walk) Cover
3.1 Min-Max Stacker Crane Cover Problem
3.2 Min-Max Stacker Crane Walk Cover Problem
4 Minimum Stacker Crane (Walk) Cover Problem
5 Conclusions
References
Succinct Data Structures for Series-Parallel, Block-Cactus and 3-Leaf Power Graphs
1 Introduction
1.1 Previous Work
1.2 Our Main Contribution
2 Preliminaries and Main Techniques
2.1 Tree Covering
2.2 Graph Representation Using Tree Covering
3 Series-Parallel Graphs
4 Block/Cactus/Block-Cactus Graphs
5 3-leaf Power Graph
6 Conclusions
References
Streaming Submodular Maximization Under Differential Privacy Noise
1 Introduction
2 Preliminaries
3 Related Work
4 The DP-SS Algorithm
4.1 DP-SS with Known OPTF
4.2 The Final DP-SS Under DP Noise
5 Experiments
5.1 Experimental Setup
5.2 Experimental Results
References
Online Bottleneck Semi-matching
1 Introduction
2 Preliminaries
3 Online Bottleneck Semi-matching with Arbitrary Number of Servers
4 Online Bottleneck Semi-matching with Two Servers
5 Online Bottleneck Semi-matching on a Line with Three Servers
6 Conclusion
References
Optimal Due Date Assignment Without Restriction and Convex Resource Allocation in Group Technology Scheduling
1 Introduction
2 Problem Formulation
3 Preliminary Analysis
4 The Optimal Schedule
4.1 Numerical Example
5 Conclusion
References
Constrained Stable Marriage with Free Edges or Few Blocking Pairs
1 Introduction
2 Preliminaries
3 Classical Complexity
3.1 -SMFE
3.2 -SMtBP
4 Parameterized Complexity
4.1 Tractable Results
4.2 Intractable Results
5 Concluding Remarks
References
Backgammon Is Hard
1 Introduction
2 Backgammon and Its Generalization
3 NP-Hardness
4 PSPACE-Hardness
5 EXPTIME-Hardness
6 Conclusion
References
Two-Facility Location Games with a Minimum Distance Requirement on a Circle
1 Introduction
1.1 Related Work
1.2 Our Results
1.3 Organization of the Paper
2 Preliminaries
3 The Circle
3.1 Maximizing the Total Utility
3.2 Maximizing the Minimum Utility
4 A Line Interval
5 Conclusions
References
Open Shop Scheduling Problem with a Non-resumable Flexible Maintenance Period
1 Introduction
2 Preliminaries
3 A 43-Approximation Algorithm
3.1 The Greedy Algorithm
3.2 Approximation Algorithm and Analysis
4 Conclusion
References
Parallel Algorithm for Minimum Partial Dominating Set in Unit Disk Graph
1 Introduction
1.1 Related Works
1.2 Our Contributions
2 A Constant Approximation Algorithm for MinPDS-UD
3 An Improved Approximation Algorithm for MinPDS-UD
4 Conclusion
References
An Improved Approximation Algorithm for Squared Metric k-Facility Location
1 Introduction
1.1 Our Results
2 Preliminaries
3 A Fractional Solution
4 Rounding
5 Conclusions
References
Parameterized Algorithms for Linear Layouts of Graphs with Respect to the Vertex Cover Number
1 Introduction
2 Preliminaries
3 Mixed s-Stack q-Queue Layout
3.1 Two Kinds of Vertices in VW
3.2 An Algorithm Based on Kernelization
3.3 The Derived Results for Some Related Problems
4 k-Arch Layout
4.1 Two Kinds of Vertices in VW
4.2 An Algorithm Based on Kernelization
5 Conclusion
References
The Fractional k-truncated Metric Dimension of Graphs
1 Introduction
2 Some Observations and Bounds on dimk,f(G)
3 dimk,f(G) of Some Graph Classes
3.1 Cycles and Graphs G with diam(G)2
3.2 Grid Graphs
3.3 Trees
4 Some Remarks and Open Problems
References
On Structural Parameterizations of the Offensive Alliance Problem
1 Introduction
1.1 Known Results
2 Hardness Results
3 No Polynomial Kernel When Parameterized by Vertex Cover Number
3.1 Proof of Theorem3
4 Conclusions
References
On the k-colored Rainbow Sets in Fixed Dimensions
1 Introduction
2 Preliminaries
3 MDkCSS is in FPT in Any Fixed Dimension
3.1 Algorithm
3.2 Maximum Weight k-rainbow Set
4 Experimental Studies
5 Enumerating All MDkCSS of Diameter at Most q
6 Approximation Algorithms
7 Discussions and Open Problems
References
Cycle-Connected Mixed Graphs and Related Problems
1 Introduction
2 Terminologies and Fundamental Lemmas
3 The Cycle-Connected Mixed Graph Problem
4 The Circuit-Connected Mixed Graph Problem
5 Cycle-Connectivity and Strong Cycle-Connectivity
6 Conclusion and Further Research
References
Directed Width Parameters on Semicomplete Digraphs
1 Introduction
2 Preliminaries
3 Directed Width Parameters
3.1 Directed Cops and Robber Games
3.2 Directed Path-Width
3.3 Directed Tree-Width
3.4 DAG-Width
3.5 Kelly-Width
3.6 Directed (Linear) Clique-Width
4 Comparison of Directed Width Parameters on Semicomplete Digraphs
4.1 DAG-Width and Directed Path-Width on Semicomplete Digraphs
4.2 Escaping Pursuit in the Jungle: Directed Path-Width, Directed Tree-Width and Kelly-Width
4.3 Directed (Linear) Clique-Width and Directed Path-Width on Semicomplete Digraphs
5 Conclusion
References
Improved Parameterized Approximation for Balanced k-Median
1 Introduction
1.1 Our Contributions
1.2 Other Related Work
1.3 Preliminaries
2 The Sampling Algorithm
3 The Connection Algorithm
4 Conclusions
References
A LP-based Approximation Algorithm for generalized Traveling Salesperson Path Problem
1 Introduction
2 Preliminaries
3 Algorithm and Analysis
3.1 Approximation Algorithm
3.2 An Improvement on 53
3.3 Tighter Analysis
4 Conclusion
References
Hardness Results of Connected Power Domination for Bipartite Graphs and Chordal Graphs
1 Introduction
2 Definitions and Preliminary Results
3 NP-completeness Results
3.1 Result for Perfect Elimination Bipartite Graphs
3.2 Result for Split Graphs
4 Algorithms for Chain Graphs and Threshold Graphs
4.1 Connected Power Domination for Chain Graphs
4.2 Connected Power Domination for Threshold Graphs
5 Lower Bound on Approximation Ratio
6 Conclusion
References
Approximation Algorithm for Min-Max Correlation Clustering Problem with Outliers
1 Introduction
2 Preliminaries
3 Algorithm and Analysis
3.1 Algorithm
3.2 Theoretical Analysis
4 Conclusions
References
Delay-Constrained Minimum Shortest Path Trees and Related Problems
1 Introduction and Problem Description
2 Terminologies and Key Lemmas
3 An Exact Algorithm to Solve the DcMSPT Problem
4 An Exact Algorithm to Solve the MDMSPT Problem
5 Conclusion and Further Research
References
On the Feedback Number of 3-Uniform Linear Extremal Hypergraphs
1 Introduction
2 Hypergraphs
3 The 3-Uniform Linear Extremal Hypergraphs
3.1 The Extremal Hypergraphs with Maximum Degree Smaller Than 3
3.2 The Extremal Hypergraphs with Maximum Degree of 3
4 Conclusion and Future Work
References
A Multi-pass Streaming Algorithm for Regularized Submodular Maximization
1 Introduction
1.1 Related Work
2 Preliminaries
3 Algorithm
4 Theoretical Analysis
5 Conclusion
References
Author Index