Computing and Combinatorics 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I

This two-volume set, LNCS 15983 and 15984, constitutes the referred proceedings of the 31st International Computing and Combinatorics Conference, COCOON 2025, held in Chengdu, China, during August 15–17, 2025.

The 54 full papers were carefully reviewed and selected from 191 submissions. COCOON 2025 provided an excellent venue for researchers working in the topical sections as follows:
Part I: Approximation Algorithms, Combinatorial Optimization, Computational Complexity, Computational Geometry, Economics and Computation.
Part II: Graph Algorithms and Graph Theory, Learning and Data-Related Theory, Parameterized Algorithms, String Algorithms and Discrete Structures.

.- Approximation Algorithms.
.- Improved Approximation Algorithms for Combinatorial Contracts with Type Constraints.
.- Approximation Algorithms for the Maximum Connected Submodular Functions.
.- Approximating per-scenario bound for the two-stage stochastic facility location problem.
.- Bilevel adversarial scheduling problem on parallel machines.
.- A Randomized FPT Approximation Algorithm for Sorting Unsigned Genomes by Translocations: Breaking the 1.375 Approximation Barrier.
.- On Online Approximation Algorithms for Two-Stage Bins.
.- An Improved Approximation Algorithm for the Minimum k-Star Partition Problem.
.- Doubly Constrained Fair Clustering for General p-Norms.
.- Combinatorial Optimization
.- Discrete Effort Distribution via Regret-Enabled Greedy Algorithm.
.- Improving Local Search for Weighted Partial MaxSAT by Initializing with Historical Information.
.- Regularized Submodular Maximization over Integer Lattice.
.- Adaptive Weighting-based Local Search for Route Number Minimization for Vehicle Routing Problem with Time Windows.
.- Computational Complexity.
.- Hunting a rabbit is hard.
.- A Nearly-4 log n Depth Lower Bound for Formulas With Restriction on Top.
.- Average-Case Deterministic Query Complexity of Boolean Functions with Fixed Weight.
.- Optimal Framework for Clustering with Noisy Queries.
.- Computational Geometry.
.- Minimum-Membership Geometric Dominating Set: Complexity and Algorithms.
.- New Lower Bound and Algorithm for Online Geometric Hitting Set Problem.
.- Erd?os-Szekeres Maker-Breaker Games.
.- Minimum Membership Geometric Set Cover in the Continuous Setting.
.- Economics and Computation.
.- On the Distortion of Multi-winner Election Using Single-Candidate Ballots.
.- Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities.
.- Equivalence of Connected and Peak-Pit Maximal Condorcet Domains.
.- On the Oscillations in Cournot Games with Best Response Strategies.
.- Simultaneous All-Pay Auctions with Budget Constraints.
.- Online Budget Allocation Maximization Problem on Two Uniform Machines with a Common Due Date.