Accepted Papers for APPROX 2023

  • Amir Abboud, Mohammadhossein Bateni, Vincent Cohen-Addad, Karthik C. S. and Saeed Seddighin. On Complexity of 1-Center in Various Metrics
  • Kamesh Munagala, Govind S. Sankar and Erin Taylor. Probabilistic Metric Embedding via Metric Labeling
  • Karthekeyan Chandrasekaran and Weihang Wang. Approximating submodular k-partition via principle partition sequence
  • Lap Chi Lau, Robert Wang and Hong Zhou. Experimental Design for Any p-Norm
  • George Karakostas and Stavros Kolliopoulos. Approximation algorithms for maximum weighted throughput on unrelated machines
  • Morteza Monemizadeh. Facility Location in the Sublinear Geometric Model
  • Tanvi Bajpai and Chandra Chekuri. Bicriteria Approximation Algorithms for Priority Matroid Median
  • Elena Grigorescu, Nithish Kumar and Young-San Lin. Approximation Algorithms for Directed Weighted Spanners
  • Matej Lieskovský, Jiří Sgall and Andreas Emil Feldmann. Approximation Algorithms and Lower Bounds for Graph Burning
  • Alexander Golovnev, Siyao Guo, Spencer Peters and Noah Stephens-Davidowitz. The (im)possibility of simple search-to-decision reductions for approximation problems
  • Eden Chlamtac, Yury Makarychev and Ali Vakilian. Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
  • Anupam Gupta, Amit Kumar and Debmalya Panigrahi. Efficient Algorithms and Hardness Results for the Weighted k-server Problem
  • Zachary Friggstad and Ramin Mousavi. A Constant-Factor Approximation for Quasi-bipartite Directed Steiner Tree on Minor-Free Graphs
  • Ishan Bansal, Joe Cheriyan, Logan Grout and Sharat Ibrahimpur. Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
  • Noah Singer. Oblivious algorithms for the Max-kAND problem
  • Felix Höhne and Rob van Stee. A 10/7-approximation for discrete bamboo garden trimming and continuous trimming on star graphs
  • Lindsey Deryckere and Seeun William Umboh. Online Matching with Set and Concave Delays
  • Anita Dürr, Nicolas El Maalouly and Lasse Wulf. An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
  • Josefine Foos, Stephan Held and Yannik Spitzley. Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
  • Danish Kashaev and Guido Schaefer. Round and Bipartize for Vertex Cover Approximation
  • Nikhil Ayyadevara, Nikhil Bansal and Milind Prabhu. On Minimizing Generalized Makespan on Unrelated Machines
  • Ilan Doron-Arad, Ariel Kulik and Hadas Shachnai. An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding
  • Kalen R Patton, Matteo Russo and Sahil Singla. Submodular Norms with Applications to Online Facility Location and Stochastic Probing
  • Chandra Chekuri and Kent Quanrud. Independent Sets in Elimination Graphs with a Submodular Objective
  • Sepideh Mahabadi and Shyam Narayanan. Improved Diversity Maximization Algorithms for Matching and Pseudoforest
  • Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan and Christos Tzamos. Approximating Pandora’s Box with Correlations
  • Mark de Berg, Arpan Sadhukhan and Frits Spieksma. Stable Approximation Algorithms for Dominating Set and Independent Set
  • Quanquan C. Liu, Yiduo Ke and Samir Khuller. Scalable Auction Algorithms for Bipartite Maximum Matching Problems