Articles under category:
Approximation Algorithms
Vol 18, Article 18 (pp 1-19)
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks
by Chandra Chekuri and Tanmay Inamdar
Vol 18, Article 7 (pp 1-24) [APRX-RND19 Spec Issue]
Fast and Deterministic Approximations for $k$-Cut
by Kent Quanrud
Vol 18, Article 3 (pp 1-29) [APRX-RND16 Spec Issue]
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Vol 16, Article 14 (pp 1-8) [NOTE]
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem
by Chandra Chekuri and Shi Li
Vol 16, Article 12 (pp 1-18)
Optimality of Correlated Sampling Strategies
by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan
Vol 14, Article 10 (pp 1-33) [CCC17 Spec Issue]
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
Vol 14, Article 8 (pp 1-35)
The Complexity of Computing the Optimal Composition of Differential Privacy
by Jack Murtagh and Salil Vadhan
Vol 14, Article 3 (pp 1-21) [CCC17 Spec Issue]
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
Vol 13, Article 15 (pp 1-24)
Tight Hardness of the Non-Commutative Grothendieck Problem
by Jop Briët, Oded Regev, and Rishi Saket
Vol 13, Article 14 (pp 1-17) [APRX-RND15 Spec Issue]
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
by David Felber and Rafail Ostrovsky
Vol 13, Article 13 (pp 1-31)
Nash Equilibria in Perturbation-Stable Games
by Maria-Florina Balcan and Mark Braverman
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Vol 13, Article 5 (pp 1-47) [APRX-RND13 Spec Issue]
A Pseudo-Approximation for the Genus of Hamiltonian Graphs
by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos
Vol 12, Article 17 (pp 1-25) [APRX-RND14 Spec Issue]
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
by Anand Louis and Yury Makarychev
Vol 12, Article 15 (pp 1-29) [APRX-RND14 Spec Issue]
Lowest-Degree $k$-Spanner: Approximation and Hardness
by Eden Chlamtáč and Michael Dinitz
Vol 12, Article 14 (pp 1-14) [APRX-RND15 Spec Issue]
Minimizing Maximum Flow-Time on Related Machines
by Nikhil Bansal and Bouke Cloostermans
Vol 12, Article 2 (pp 1-34)
Lattice Sparsification and the Approximate Closest Vector Problem
by Daniel Dadush and Gábor Kun
Vol 11, Article 9 (pp 241-256) [APRX-RND13 Spec Issue]
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
by Shayan Oveis Gharan and Luca Trevisan
Vol 11, Article 7 (pp 221-235) [APRX-RND12 Spec Issue]
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
by Dana Moshkovitz
Vol 11, Article 4 (pp 105-147)
Maximizing the Spread of Influence through a Social Network
by David Kempe, Jon Kleinberg, and Éva Tardos
Vol 10, Article 13 (pp 341-358) [APRX-RND12 Spec Issue]
Approximation Algorithm for Non-Boolean Max-$k$-CSP
by Konstantin Makarychev and Yury Makarychev
Vol 10, Article 11 (pp 257-295)
Efficient Rounding for the Noncommutative Grothendieck Inequality
by Assaf Naor, Oded Regev, and Thomas Vidick
Vol 9, Article 28 (pp 863-887) [Boolean Spec Issue]
A Two-Prover One-Round Game with Strong Soundness
by Subhash Khot and Muli Safra
Vol 9, Article 22 (pp 685-702)
Hamming Approximation of NP Witnesses
by Daniel Sheldon and Neal E. Young
Vol 8, Article 26 (pp 597-622)
A Constant-Factor Approximation Algorithm for Co-clustering
by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar
Vol 8, Article 24 (pp 533-565)
Solving Packing Integer Programs via Randomized Rounding with Alterations
by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan
Vol 8, Article 20 (pp 429-460) [Motwani Special Issue]
Budget-Constrained Auctions with Heterogeneous Items
by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala
Vol 8, Article 18 (pp 401-413) [Motwani Special Issue]
An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
by Julia Chuzhoy and Sanjeev Khanna
Vol 8, Article 14 (pp 321-350) [Motwani Special Issue]
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
by Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani
Vol 7, Article 5 (pp 49-74)
Metric Clustering via Consistent Labeling
by Robert Krauthgamer and Tim Roughgarden
Vol 7, Article 3 (pp 27-43)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
by Per Austrin, Subhash Khot, and Muli Safra
Vol 5, Article 4 (pp 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
Vol 4, Article 9 (pp 191-193) [COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem
by Viswanath Nagarajan
Vol 4, Article 5 (pp 111-128)
Approximation Algorithms for Unique Games
by Luca Trevisan
Vol 4, Article 2 (pp 21-51)
Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem
by Miklós Ajtai
Vol 4, Article 1 (pp 1-20)
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall
Vol 3, Article 10 (pp 197-209)
An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
by Chandra Chekuri and Martin Pál
Vol 3, Article 9 (pp 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing
by Maria-Florina Balcan and Avrim Blum
Vol 3, Article 6 (pp 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman
Vol 3, Article 3 (pp 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Vol 2, Article 13 (pp 249-266)
Correlation Clustering with a Fixed Number of Clusters
by Ioannis Giotis and Venkatesan Guruswami
Vol 2, Article 12 (pp 225-247)
Matrix Approximation and Projective Clustering via Volume Sampling
by Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang
Vol 2, Article 11 (pp 207-224)
Embedding the Ulam metric into 1
by Moses Charikar and Robert Krauthgamer
Vol 2, Article 7 (pp 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd
Vol 2, Article 4 (pp 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
Vol 2, Article 3 (pp 53-64)
An Improved Approximation Ratio for the Covering Steiner Problem
by Anupam Gupta and Aravind Srinivasan
Vol 2, Article 2 (pp 19-51)
Proving Integrality Gaps without Knowing the Linear Program
by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis
Vol 1, Article 7 (pp 119-148)
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot