COCOON 2025

Accepted Papers

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