Accepted Papers for APPROX 2022

  • Simon Apers, Pawel Gawrychowski and Troy Lee. Finding the KT partition of a weighted graph in near-linear time
  • Moran Feldman and Ariel Szarf. Maximum Matching sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model
  • Shichuan Deng and Qianfan Zhang. Ordered k-Median with Outliers
  • Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan and Santhoshini Velusamy. Sketching Approximability of (Weak) Monarchy Predicates
  • Takuro Fukunaga. Integrality gap of time-indexed linear programming relaxation for coflow scheduling
  • Roy Schwartz and Roded Zats. Fair Correlation Clustering in General Graphs
  • Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer and Santhoshini Velusamy. On sketching approximations for symmetric Boolean CSPs
  • Amartya Shankha Biswas, Talya Eden, Quanquan Liu, Slobodan Mitrović and Ronitt Rubinfeld. Massively Parallel Algorithms for Small Subgraph Counting
  • Daniel Spielman and Peng Zhang. Hardness Results for Weaver’s Discrepancy Problem
  • Michael Dinitz, Ama Koranteng and Guy Kortsarz. Relative Survivable Network Design
  • Venkatesan Guruswami, Pravesh K Kothari and Peter Manohar. Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number
  • Suprovat Ghoshal and Anand Louis. Approximating CSPs with Outliers
  • Frederick Qiu and Sahil Singla. Submodular Expectations for Negatively Dependent Distributions and Applications
  • Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka and Jan Marcinkowski. Online Facility Location with Linear Delay
  • Calum MacRury, Allan Borodin and Akash Rakheja. Prophet Matching in the Probe-Commit Model
  • Suprovat Ghoshal. The Biased Homogeneous r-Lin Problem
  • Sepehr Assadi and Hoai-An Nguyen. Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting
  • Max Klimm and Martin Knaack. Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
  • Aleksa Stankovic. Some Results on Approximability of Minimum Sum Vertex Cover
  • Michael Elkin and Chhaya Trehan. $(1+\epsilon)$-Approximate Shortest Paths in Dynamic Streams
  • Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee and Joshua Wang. Caching with Reserves
  • Kheeran K. Naidu and Vihan Shah. Space Optimal Vertex Cover in Dynamic Streams
  • Debarati Das and Barna Saha. Approximating LCS and Alignment Distance over Multiple Sequences
  • Tobias Friedrich, Davis Isaac, Nikhil Kumar, Nadym Mallek and Ziena Zeif. A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth 2 Graphs