COCOON 2025

Accepted Papers

  1. Yu Nakahata. Reconfiguring Multiple Connected Components with Size Multiset Constraints
  2. Chilei Wang, Qiang-Sheng Hua and Hai Jin. Massively Parallel Approximate Steiner Tree Algorithms
  3. Zizheng Guo, Jun Wu, Pengyu Chen, Yanzhang Fu and Dongjing Miao. Data Debugging is NP-hard for Classifiers Trained with SGD
  4. Haowei Wu, Yuan Li and Yi Yang. Average-Case Deterministic Query Complexity of Boolean Functions with Fixed Weight
  5. Tong Xu, Wei Yu and Zhaohui Liu. An Improved Approximation Algorithm for the Minimum $k$-Star Partition Problem
  6. Xia Wen, Jorik Jooken, Jan Goedgebeur, Iain Beaton, Ben Cameron and Shenwei Huang. Critical $(P_5,W_4)$-Free Graphs
  7. Jianqi Zhou, Zhongyi Zhang, Yinghui Wen and Jiong Guo. From Metric to General Graphs: FPT Constant-Factor Approximation Algorithms for Three Location Problems
  8. Jianqi Zhou, Zhongyi Zhang and Jiong Guo. An FPT Factor-11 Approximation Algorithm for TSP
  9. Yaqiao Li. Undecidability of polynomial inequalities in subset densities and additive energies
  10. Walid Ben-Ameur, Harmender Gahlawat and Alessandro Maddaloni. Hunting a rabbit is hard
  11. Zhengyang Liu, Haolin Lu, Liang Shan and Zihe Wang. On the Oscillations in Cournot Games with Best Response Strategies
  12. Markus Lohrey and Andreas Rosowski. Finding cycle types in permutation groups with few generators
  13. Zichun Ye, Chihao Zhang and Jiahao Zhao. Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
  14. Baohua Niu, Yan Wang, Baolei Cheng, Hai Liu, Bai Yin, Jianxi Fan and Xinyang Cai. Fault diagnosability evaluation of BCCC data center networks
  15. Xiaofei Liu and Weidong Li. Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints
  16. Hao Wu. A Nearly-$4\log n$ Depth Lower Bound for Formulas With Restriction on Top
  17. Zheng Chen, Bin Deng, Bo Li, Minming Li, Weidong Li and Guochuan Zhang. Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities
  18. Gennaro Auricchio, Zeyu Ren, Zihe Wang and Jie Zhang. On the Distortion of Multi-winner Election Using Single-Candidate Ballots
  19. Guangwei Wu, Hongyun He, Guozhen Rong, Feng Shi and Yongjie Yang. On Online Approximation Algorithms for Two-Stage Bins
  20. Yuxuan Wang, Yunhao Li, Zhouxing Su, Junwen Ding, Qingyun Zhang and Zhipeng Lü. Adaptive Weighting-based Local Search for Route Number Minimization for Vehicle Routing Problem with Time Windows
  21. Yang Hu, Bo Ning and Xiumin Wang. A sufficient condition for the existence of two completely independent spanning trees
  22. Xue Chen, Wenxuan Shu and Haoyu Wang. Revisit the Partial Coloring Method: Prefix Spencer and Sampling
  23. Guanhao Li. Equivalence of Connected and Peak-Pit Maximal Condorcet Domains
  24. Long-Shang Cho, Kai-Wei Chang and Chin Lung Lu. A Sparse Dynamic Programming Algorithm for Solving the Coding Sequence Design Problem
  25. Yaru Yang, Honglin Ding and Wentao He. Online Budget Allocation Maximization Problem on Two Uniform Machines with a Common Due Date
  26. Eric Rivals and Pengfei Wang. Counting overlapping pairs of strings
  27. Lunhao Zhang, Pengzhi Gao and Peng Zhang. Doubly Constrained Fair Clustering for General Norms
  28. Tingting Zhang, Yuan Yuan, Xiao Zhang, Yifei Zou, Zhipeng Cai and Dongxiao Yu. A Robust Distributed Minimax Learning Method against Model Poisoning Attacks
  29. Panfeng Liu and Biaoshuai Tao. Parameterized Complexity of Influence Maximization
  30. Yan Liu, Ying Qin and Zihe Wang. Simultaneous All-Pay Auctions with Budget Constraints
  31. Ruiqing Sun. Bilevel adversarial scheduling problem on parallel machines
  32. Menghua Jiang, Rui Zhang and Yin Chen. Improving Local Search for Weighted Partial MaxSAT by Initializing with Historical Information
  33. Siu-Wing Cheng and Man Ting Wong. A Dynamic Working Set Method for Compressed Sensing
  34. Zhicheng Liu, Yang Lv, Yapu Zhang and Zhenning Zhang. Regularized Submodular Maximization over Integer Lattice
  35. Yinghui Wen, Xin Tong, Jiong Guo and Aizhong Zhou. Pareto Optimal Matching with Multilayer Preferences: How Hard Can It Be?
  36. Yifei Wang, Jiayan Zhu, Yao Xu, Xin Li and Jiamou Liu. Redefining Entity Integration: Theoretical Insights for GNN-based Recommender Systems
  37. Chengcheng Sun, Haitao Jiang, Guojun Li and Daming Zhu. A Randomized Fixed-Parameter Tractable Algorithm for Sorting Unsigned Genomes by Translocations: Breaking the 1.375 Approximation Barrier
  38. Yuan Wang, Jianhang Sun, Zhipeng Lü, Zhouxing Su, Junwen Ding and Qingyun Zhang. A Multi-start Variable Neighborhood Tabu Search Algorithm for the Cyclic Bandwidth Problem
  39. Qinqin Gong, Chunlin Hao, Donglei Du and Ruiqi Yang. Improved Approximation Algorithms for Combinatorial Contracts with Type Constraints
  40. Qinqin Gong, Zixuan Wang, Yang Lv and Ruiqi Yang. Approximation Algorithms for the Maximum Connected Submodular Functions
  41. Tiantian Li, Siqi Jiang, Haitao Jiang and Daming Zhu. Longest Double-Bounded (k]-tuple Common Substrings
  42. Sathish Govindarajan, Mayuresh Patle and Siddhartha Sarkar. Minimum Membership Geometric Set Cover in the Continuous Setting
  43. Wenfeng Lai, Haitao Jiang, Daming Zhu and Binhai Zhu. Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals
  44. Mengzhen Li, Chenchen Wu, Dachuan Xu and Yicheng Xu. Approximating per-scenario bound for the two-stage stochastic facility location problem
  45. Jinghui Xia and Zengfeng Huang. Optimal Framework for Clustering with Noisy Queries
  46. Faisal Abu-Khzam, Tom Davot, Lucas Isenmann and Sergio Thoumi. On the Complexity of 2-Club Cluster Editing with Vertex Splitting
  47. Aleksa Džuklevski, Dömötör Pálvölgyi, Alexey Pokrovskiy, Csaba Toth, Tomas Vallla and Lander Verlinde. Erdős-Szekeres Maker-Breaker Games
  48. Ting Liang, Xiaoliang Wu, Junyu Huang and Qilong Feng. Coresets for k-Median of Lines with Group Fairness Constraints
  49. Bhavya Bansal, Raghunath Reddy Madireddy and Supantha Pandit. Minimum-Membership Geometric Dominating Set: Complexity and Algorithms
  50. Ruixi Luo, Taikun Zhu and Kai Jin. Sum-of-Max Chain Partition of a Tree
  51. Minati De, Ratnadip Mandal and Satyam Singh. New Lower Bound and Algorithm for Online Geometric Hitting Set Problem
  52. Pan Peng and Kefan Yu. Testing Some First-Order Logic Properties on Sparse Graphs
  53. Feng Shi, Yicong Zhu, Guangwei Wu, Jingyi Liu and Jianxin Wang. Improved Parameterized Algorithms for Scheduling with Precedence Constraints and Time Windows
  54. Song Cao, Taikun Zhu and Kai Jin. Discrete Effort Distribution via Regrettable Greedy Algorithm