Articles under category:
Approximation Algorithms
 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
 Vol 13, Article 10 (pp 1-19) On the Hardness of Approximating Balanced Homogenous 3-Lin
 Vol 13, Article 5 (pp 1-47) [APRX-RND13 Spec Issue] A Pseudo-Approximation for the Genus of Hamiltonian Graphs
 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
 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
 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
 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
 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
 Vol 8, Article 24 (pp 533-565) Solving Packing Integer Programs via Randomized Rounding with Alterations
 Vol 8, Article 20 (pp 429-460) [Motwani Special Issue] Budget-Constrained Auctions with Heterogeneous Items
 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
 Vol 7, Article 5 (pp 49-74) Metric Clustering via Consistent Labeling
 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
 Vol 4, Article 5 (pp 111-128) Approximation Algorithms for Unique Games
 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
 Vol 4, Article 1 (pp 1-20) Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
 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
 Vol 3, Article 6 (pp 103-128) Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
 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
 Vol 2, Article 12 (pp 225-247) Matrix Approximation and Projective Clustering via Volume Sampling
 Vol 2, Article 11 (pp 207-224) Embedding the Ulam metric into ℓ1
 Vol 2, Article 7 (pp 137-146) An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
 Vol 2, Article 4 (pp 65-90) Rank Bounds and Integrality Gaps for Cutting Planes Procedures
 Vol 2, Article 3 (pp 53-64) An Improved Approximation Ratio for the Covering Steiner Problem
 Vol 2, Article 2 (pp 19-51) Proving Integrality Gaps without Knowing the Linear Program
 Vol 1, Article 7 (pp 119-148) Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot