Accepted papers for APPROX 2025

  • Kinter Ren and Mohammad Salavatipour. Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
  • Aniket Basu Roy. Covering Simple Orthogonal Polygons with Rectangles
  • Tamio-Vesa Nakajima and Stanislav Živný. Maximum And- vs. Even-SAT
  • Chandra Chekuri, Rhea Jain, Sepideh Mahabadi and Ali Vakilian. Streaming Algorithms for Network Design
  • Aditya Anand, Euiwoong Lee, Davide Mazzali and Amatya Sharma. Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
  • Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro and Florian Speelman. QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
  • Rafail Ostrovsky, Yuval Rabani and Yoav Siman Tov. Budget and Profit Approximations for Spanning Tree Interdiction
  • N. Efe Cekirge, William H. Gay and David P. Woodruff. Multipass Linear Sketches for Geometric LP-Type Problems
  • Miriam Fischer, Dario Paccagnan and Cosimo Vinci. Optimal Competitive Ratio for Optimization Problems with Congestion Effects
  • Waldo Gálvez, Roberto Oliva and Victor Verdugo. Improved Approximation Guarantees for Advertisement Placement
  • Francesco Agrimonti, Marco Bressan and Tommaso D’Orsi. On Finding Randomly Planted Cliques in Arbitrary Graphs
  • Xiang Liu and Kasturi Varadarajan. Relational Approximations for Subspace Primitives
  • Yury Makarychev, Madhusudhan Reddy Pittu and Ali Vakilian. Max-Cut with Multiple Cardinality Constraints
  • Sina Kalantarzadeh and Nikhil Kumar. Improved Lower Bounds on Multiflow-Multicut Gaps
  • Romain Bourneuf, Julien Cocquet, Chaoliang Tang and Stéphan Thomassé. A Polynomial-Time Approximation Algorithm for Complete Interval Minors
  • Tommaso D’Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan and Jiyu Zhang. Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
  • Nicholas Kocurek and Peter Manohar. Spectral Refutations of Semirandom k-LIN over Larger Fields
  • Sina Kalantarzadeh, Nathan Klein and Victor Reis. A Randomized Rounding Approach for DAG Edge Deletion
  • Ian DeHaan, Neng Huang and Euiwoong Lee. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
  • Jungho Ahn, Ian DeHaan, Eun Jung Kim and Euiwoong Lee. Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
  • Nathan Klein and Mehrshad Taziki. Dual Charging for Half-Integral TSP
  • Elena Grigorescu, Nithish Kumar Kumar and Young-San Lin. Directed Buy-at-Bulk Spanners
  • Sayan Bandyapadhyay and Tianzhi Chen. Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints
  • Nathan Ju and Ansh Nagda. Improved approximation algorithms for the EPR Hamiltonian
  • Tanvi Bajpai, Chandra Chekuri and Pooja Kulkarni. Covering a Few Submodular Constraints and Applications
  • Mads Anker Nielsen, Lars Rohwedder and Kevin Schewior. Non-Adaptive Evaluation of k-of-n Functions: Tight Gap and a Unit-Cost PTAS
  • Fredie George, Anand Louis and Rameesh Paul. Triangles Improve 0.878 Approximation for Maxcut