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

✍ Scribed by Weili Wu (editor), Jianxiong Guo (editor)

• Publisher: Springer
• Year: 2023
• Tongue: English
• Leaves: 535
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Preface
Organization
Contents – Part I
Contents – Part II
Optimization in Graphs
An Efficient Local Search Algorithm for Correlation Clustering on Large Graphs
1 Introduction
1.1 Related Work
2 Previous Algorithms
2.1 Pivot
2.2 LocalSearch
3 InnerLocalSearch
3.1 InnerLocalSearch and Pivot
4 Experiments
5 Conclusion
References
Algorithms on a Path Covering Problem with Applications in Transportation
1 Introduction
2 Problem Formulation
3 NP-Hardness Result for MaxPathCov, MinPathAuto and s-MaxPathCov
4 Polynomial Time Algorithm for MaxCov and MinPathAuto
5 Approximation Algorithm for S-MaxCov
6 Conclusions
References
Faster Algorithms for Evacuation Problems in Networks with a Single Sink of Small Degree and Bounded Capacitated Edges
1 Introduction
2 Preliminaries
2.1 Notations and Problem Definition
2.2 Maximum Dynamic Flows
3 Computing the Minimum Feasible Time Horizon
3.1 Definition and Property of
3.2 Algorithms
4 An Algorithm for Finding a Quickest Flow
4.1 Base Polytope
4.2 Relationship Between Quickest Flows and Base Polytopes
4.3 Algorithms
5 Conclusion
References
An O(logn)-Competitive Posted-Price Algorithm for Online Matching on the Line
1 Introduction
1.1 Additional Related Work
2 Modified Doubled Harmonic Description
3 Monotonicity Analysis
4 Cost Analysis
A Remedying Some Assumptions
A.1 Minimum Distance 1 Between Servers
A.2 Requests Appear at Server Locations
B Proof that Doubled Harmonic is Not Monotone
C Auxiliary Lemma for Lemma 4
D Cost Analysis Definitions
E Bounding Non-Trigger Costs
F Bounding Trigger Costs
G Proving Theorem 2
References
Online Dominating Set and Coloring
1 Introduction
1.1 Preliminaries
1.2 Related Work
1.3 Our Contributions
2 Dominating Set and Its Variants
2.1 Minimum Dominating Set
2.2 Minimum Connected Dominating Set
2.3 Lower Bound of the MCDS Problem
3 Algorithm for the Minimum Coloring Problem
4 Value of for Families of Geometric Objects
5 Applications
6 Conclusion
References
Near-Bipartiteness, Connected Near-Bipartiteness, Independent Feedback Vertex Set and Acyclic Vertex Cover on Graphs Having Small Dominating Sets
1 Introduction
2 On Graphs Having a Dominating Edge
3 On P5-Free Graphs
References
Exactly k MSTs: How Many Vertices Suffice?
1 Introduction
2 Preliminaries
2.1 Notation
2.2 Known Lower Bounds
2.3 Connection to Arithmetic Expressions
2.4 Upper Bounds
3 Minimal Weighted Graphs with Prime Number of MSTs
4 Study of the Spectrum
5 Conclusion
References
Minimum Monotone Tree Decomposition of Density Functions Defined on Graphs
1 Introduction
2 Preliminaries
2.1 Problem Definition
2.2 Greedy Algorithm for Density Trees ch8baryshnikov2018minimal
2.3 Additional Property of Monotone Sweeping Operation
3 Hardness Results
3.1 Approximation Hardness
3.2 Variations of Minimum M-Tree Sets are Also NP-Complete
4 Algorithms
4.1 Additive Error Approximation Algorithms
4.2 Approximation Algorithm for Minimum SM-Tree Sets of Density Cactus Graphs
5 Conclusion
A Proof of Claim 2.3
B Complexity
B.1 Proof of Theorem 5: CM-Tree Sets
B.2 Proof of Theorem 5: SM-Tree Sets
B.3 Proof of Theorem 5: FM-Tree Sets
C Set Cover Intersection 1 Approximation Bound ch8kumar2000hardness
D Proof of Theorem 2
E Proof of Theorem 3
F Algorithms
F.1 Naive Approximation Algorithm
References
Scheduling
Exact and Approximation Algorithms for the Multi-depot Data Mule Scheduling with Handling Time and Time Span Constraints
1 Introduction
1.1 Related Work
1.2 Our Results
2 Preliminaries
3 Uniform 2-Depot DMSTC on a Path
4 Non-uniform DMSTC on a Path
5 Multi-depot DMSTCl on a Path
6 Multi-depot DMSTCl on a Cycle
7 Conclusions
References
Two Exact Algorithms for the Packet Scheduling Problem
1 Introduction
2 Related Work
3 GRD: Scheduling Packets on Arborescence and Anti-Arborescence Forests
3.1 The Ideas
3.2 The Algorithm
3.3 The Analysis
4 An Optimal Algorithm for the General Case
4.1 The Ideas
4.2 The Algorithm and Its Analysis
5 Conclusions
References
Improved Scheduling with a Shared Resource
1 Introduction
1.1 Model Description and Preliminaries
1.2 Related Work
1.3 Our Contribution and Methods
2 Makespan Minimization
3 Total Completion Time Minimization
3.1 Analysis via a Bounded Fractionality Gap
3.2 The Fractionality Gap of Line Schedules
References
An Energy-Efficient Scheduling Method for Real-Time Multi-workflow in Container Cloud
1 Introduction
2 Problem Formulation
2.1 Workflow Modeling
2.2 Service Instance Modeling
2.3 Workflow Scheduling Model
3 Real-Time Multi-workflow Energy-Efficient Scheduling Algorithm
3.1 Scheduling Architecture
3.2 Request Preprocessor
3.3 Task Pool
3.4 Re-scheduling Trigger
3.5 Scheduling Decision-Maker
4 Performance Evaluation
4.1 Experimental Setup
4.2 Comparison Algorithm
4.3 Simulation Results
5 Conclusion
A Detailed Pseudocode of the Proposed Algorithm
References
Set-Related Optimization
Weakly Nondominated Solutions of Set-Valued Optimization Problems with Variable Ordering Structures in Linear Spaces
1 Introduction
2 Preliminaries and Lemmas
3 Scalarization
4 Duality
5 Conclusions
References
The MaxIS-Shapley Value in Perfect Graphs
1 Introduction
1.1 Background
1.2 Related Work
1.3 Contribution
2 Preliminaries
3 Computational Complexity
4 Algorithms
4.1 Parameterized Algorithm
4.2 O(n4) Algorithm for Graphs of Degree at Most Two
4.3 Approximation Algorithm
5 Conclusion
References
Asteroidal Sets and Dominating Paths
1 Introduction
2 Preliminaries
3 Dominating Pairs and Diametral Paths
4 Cut Sets in HDP Graphs
4.1 Asteroidal Paths and Dominating Pairs
4.2 On Networks and Faster Recognition of Chordal HDP Graphs
References
A Novel Approximation Algorithm for Max-Covering Circle Problem
1 Introduction
2 Preliminaries
3 Symmetrical Rectilinear Polygon Construction
4 Algorithm for MaxC-SRP Problem
5 Approximation Algorithm for MaxC-C Problem
5.1 Points with Unit Weight
5.2 Weighted Points
6 Conclusion
References
GAMA: Genetic Algorithm for k-Coverage and Connectivity with Minimum Sensor Activation in Wireless Sensor Networks
1 Introduction
2 Related Work
3 Preliminaries
3.1 Key Terminology and Notation
3.2 Assumptions
4 Genetic Algorithm
4.1 Coverage Model
4.2 Genetic Algorithm
4.3 Terminating Conditions
4.4 Fitness Function
4.5 Time Complexity
5 Simulation
5.1 Coverage Degree Vs. Number of Active Sensors
5.2 Sensing Range Vs. Number of Active Sensors
6 Conclusion and Future Work
References
Simple Heuristics for the Rooted Max Tree Coverage Problem
1 Introduction
1.1 Related Work
1.2 Our Results
2 NP-Hardness and Bi-criteria Approximation
3 CMSA Heuristic for Rooted MTC
3.1 An MILP Model for Rooted MTC
3.2 The CMSA Heuristic
3.3 Generate a Random Tree
4 Two Greedy Algorithms
4.1 Greedy Algorithm Based on Prim
4.2 Greedy Algorithm Based on Average Cost
5 Experimental Evaluation
6 Rooted MTC on Trees
7 Conclusions
References
Efficient Algorithms for k-Submodular Function Maximization with p-System and d-Knapsack Constraint
1 Introduction
2 Preliminaries
3 k-Submodular Maximization Under the p-System Constraint
4 k-Submodular Maximization Under the Intersection of p-System and d-Knapsack Constraints
5 Improved Algorithm for k-Submodular Maximization Under the Intersection of p-System and d-Knapsack Constraints
6 Conclusion
References
Data Summarization Beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization
1 Introduction
1.1 Related Work
2 Problem Formulation
3 Algorithm Design and Analysis
3.1 Performance Analysis
3.2 Enhanced Results for Monotone Case
References
Greedy+Max: An Efficient Approximation Algorithm for k-Submodular Knapsack Maximization
1 Introduction
2 Preliminaries
3 Greedy+Max Algorithm
4 Approximations
5 Conclusion
References
Applied Optimization and Algorithm
Improved Lower Bound for Estimating the Number of Defective Items
1 Introduction
1.1 Old and New Techniques
2 Definitions and Notation
3 The Lower Bound
3.1 Lower Bound for Randomized Algorithm
4 Conclusion
References
Popularity on the Roommate Diversity Problem
1 Introduction
1.1 Our Results
2 Preliminaries
2.1 Roommate Diversity Problem
2.2 Popularity
2.3 Exact Cover by 3-Sets Problem
3 Room Size Two
4 Strict Popularity
4.1 Roommate Diversity Game
4.2 Predefined Outcomes
4.3 Hardness
5 Mixed Popularity
6 Popularity
7 Conclusion
References
On Half Guarding Polygons
1 Introduction and Related Work
1.1 Notation/Definitions
1.2 Our Results
2 VC Dimension
2.1 VC Dimension of Terrains
2.2 VC Dimension of Monotone Polygons
3 Art Gallery Theorems
4 Exact Algorithm for Half Guarding Spiral Polygons
4.1 Vertical Edges
References
Dynamic Programming for the Fixed Route Hybrid Electric Aircraft Charging Problem
1 Introduction
2 The Fixed Route Hybrid Electric Aircraft Charging Problem (FRHACP)
3 Related Work
4 Dynamic Programming Algorithm
4.1 Minimizing Total Cost
4.2 Gradient Descent Post-treatment
5 Experiments
5.1 Experimental Setup
5.2 Instances
5.3 Results
6 Conclusion
References
Algorithms for the Ridesharing with Profit Constraint Problem
1 Introduction
2 Preliminaries
3 RPC1 Variant - Capacity of One
4 RPC+ Variant
5 Numerical Experiments
5.1 Create Test Instances
5.2 Computational Results
References
Multi-Candidate Carpooling Routing Problem and Its Approximation Algorithms
1 Introduction
2 Problem Formulation and Complexity Hierarchy
2.1 Basic Concepts and Definitions
2.2 Problem Formulation and NP Hardness Proof
2.3 Problem Generalization to Variants of TSP
2.4 Complexity Hierarchy of Related TSP Variants
3 Discussion of Previous Work
4 A 4-Approximation Algorithm for Symmetric CRP
4.1 Existing 1.5-Approximation Algorithm for the TSP-Path
4.2 Approximation Algorithm for Symmetric CRP
4.3 Approximation Ratio Analysis for Symmetric CRP
5 A (5 + )-Approximation Algorithm for Planar MCRP
5.1 Existing PTAS for Planar Group Steiner Tree
5.2 Constant-Approximation Algorithm Design for MCRP
5.3 Approxiamtion Ratio Analysis for MCRP
6 An Exact Algorithm for MCRP
7 Conclusion and Future Work
References
Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs
1 Introduction
1.1 Definition and Motivation
1.2 Our Contribution
1.3 Related Work
2 Preliminaries
2.1 Definitions, Terminologies, and Notation
2.2 Fractional Hedonic Game
3 Maximizing Utilitarian Welfare on Block Graphs: Characterization
4 Maximizing Utilitarian Welfare on Block Graphs: Algorithm
4.1 Block-Cut Tree
4.2 Recurrence Relations: Overviews
4.3 Recurrence Relations in the Block Nodes
5 Graphs of Bounded Treewidth or Vertex Cover Number
5.1 Maximizing Utilitarian Welfare
5.2 Maximizing Egalitarian Welfare
References
The Line-Constrained Maximum Coverage Facility Location Problem
1 Introduction
2 Preliminaries
3 Algorithm for Our Problem
3.1 Reduction to Maximum k-Link Path Problem
3.2 Computing OPT(1, h, j) for j=h+1,…,2n
3.3 Description of Overall Algorithm
4 Convex Monge Property of OPT(1, h, j)
5 Conclusion
References
Graph Planer and Others
On Connectedness of Solutions to Integer Linear Systems
1 Introduction
2 Preliminaries
2.1 Our Contribution
3 Proof of Theorem 1
4 Proof of Theorem 2
4.1 Expansion Lemma
4.2 Two Rows
4.3 Two Columns
4.4 Three Rows
References
An Exact Algorithm for the Line-Constrained Bottleneck k-Steiner Tree Problem
1 Introduction
2 Properties of Bottleneck Steiner Trees
3 The LcB1StT Problem
4 The LcBkStT Problem
5 Conclusion
References
The Longest Subsequence-Repeated Subsequence Problem
1 Introduction
2 Preliminaries
3 A Polynomial-Time Solution for LSRS
3.1 Solution for the LSRS Problem
3.2 An O(n6) Time Bound for the Longest Cubic Subsequences of All Substrings of the Input String
4 The Variants of LSRS
4.1 LSRS+(4) is NP-Hard
4.2 LSRS+(3) is Polynomially Solvable
5 Concluding Remarks
References
An Approximation Algorithm for Covering Vertices by 4+-Paths
1 Introduction
1.1 Our Contribution and Design Highlights
2 Basic Definitions
3 The Algorithm for MPC4+v
3.1 Modifying H and M
3.2 Bad Components and Rescuing Them
3.3 Structure of Composite Components of H+C
3.4 Operations for Modifying Critical Components
3.5 Bounding opt(G)
4 Summary of the Algorithm
References
V-Words, Lyndon Words and Substring circ-UMFFs
1 Introduction
2 Preliminaries
3 V-order
4 UMFF and Circ-UMFF Theory
5 V-words, Lyndon Words and Circ-UMFF
6 Substring circ-UMFF: Generalization of circ-UMFF
7 Galois Words
8 Concluding Comments
References
The Two-Center Problem of Uncertain Points on Trees
1 Introduction
1.1 Related Work
1.2 Our Approach
2 Preliminaries
3 The Decision Algorithm
3.1 The First Pruning Step
3.2 Pruning Uncertain Points
3.3 Wrapping Things Up
3.4 Lemma 6 and Lemma 7
4 Computing Centers q1 and q2
References
Space-Time Graph Planner for Unsignalized Intersections with CAVs
1 Introduction
2 Related Work
3 Problem Statement
4 The Space Time Graph Methodology for Trajectory Search
4.1 Collision Avoidance and Graph Representation
4.2 Discretized Graph and Discrete Time
4.3 The Space-Time Graph
4.4 The Fastest Trajectory Planner Algorithm
4.5 planRequests: Top Level Algorithm
4.6 computePath: The Shortest Space-Time Path Algorithm
5 Performance Evaluation
6 Conclusions
References
The Two Sheriffs Problem: Cryptographic Formalization and Generalization
1 Introduction
1.1 Background
1.2 Motivation and Our Contribution
1.3 Organization
2 Formalization of the Multi-Sheriff Problem
2.1 Settings of the Multi-Sheriff Problem
2.2 Multi-Sheriff Problem Protocol Construction
2.3 Requirements of the Multi-Sheriff Problem
3 BHW Protocols for Two Sheriffs Problem
3.1 Overview of the BHW Protocol
4 Our Solution for Multi-Sheriffs Problem
4.1 Observation and Our Construction Idea
4.2 Construction of Our Protocol
4.3 Proof for Correctness and Secrecy
4.4 Extension of Our Protocol
References
Author Index