Articles under category:
Approximation Algorithms
Approximation Algorithms
Vol 11, Article 7 (pp 221235)
[APRXRND12 Spec Issue]
The Projection Games Conjecture and the NPHardness of ln $n$Approximating SetCover by Dana Moshkovitz 
Vol 11, Article 4 (pp 105147)
Maximizing the Spread of Influence through a Social Network by David Kempe, Jon Kleinberg, and Éva Tardos 
Vol 10, Article 13 (pp 341358)
[APRXRND12 Spec Issue]
Approximation Algorithm for NonBoolean Max$k$CSP by Konstantin Makarychev and Yury Makarychev 
Vol 10, Article 11 (pp 257295)
Efficient Rounding for the Noncommutative Grothendieck Inequality by Assaf Naor, Oded Regev, and Thomas Vidick 
Vol 9, Article 28 (pp 863887)
[Boolean Spec Issue]
A TwoProver OneRound Game with Strong Soundness by Subhash Khot and Muli Safra 
Vol 9, Article 22 (pp 685702)
Hamming Approximation of NP Witnesses by Daniel Sheldon and Neal E. Young 
Vol 8, Article 26 (pp 597622)
A ConstantFactor Approximation Algorithm for Coclustering by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar 
Vol 8, Article 24 (pp 533565)
Solving Packing Integer Programs via Randomized Rounding with Alterations by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan 
Vol 8, Article 20 (pp 429460)
[Motwani Special Issue]
BudgetConstrained Auctions with Heterogeneous Items by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala 
Vol 8, Article 18 (pp 401413)
[Motwani Special Issue]
An $O(k^3\log n)$Approximation Algorithm for VertexConnectivity Survivable Network Design by Julia Chuzhoy and Sanjeev Khanna 
Vol 8, Article 14 (pp 321350)
[Motwani Special Issue]
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality by Sariel HarPeled, Piotr Indyk, and Rajeev Motwani 
Vol 7, Article 5 (pp 4974)
Metric Clustering via Consistent Labeling by Robert Krauthgamer and Tim Roughgarden 
Vol 7, Article 3 (pp 2743)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs by Per Austrin, Subhash Khot, and Muli Safra 
Vol 5, Article 4 (pp 83117)
SDP Gaps and UGChardness for MaxCutGain by Subhash Khot and Ryan O'Donnell 
Vol 4, Article 9 (pp 191193)
[COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem by Viswanath Nagarajan 
Vol 4, Article 5 (pp 111128)
Approximation Algorithms for Unique Games by Luca Trevisan 
Vol 4, Article 2 (pp 2151)
Optimal lower bounds for the KorkineZolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem by Miklós Ajtai 
Vol 4, Article 1 (pp 120)
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 197209)
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 179195)
Approximation Algorithms and Online Mechanisms for Item Pricing by MariaFlorina Balcan and Avrim Blum 
Vol 3, Article 6 (pp 103128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman 
Vol 3, Article 3 (pp 4560)
On the Hardness of Satisfiability with Bounded Occurrences in the PolynomialTime Hierarchy by Ishay Haviv, Oded Regev, and Amnon TaShma 
Vol 2, Article 13 (pp 249266)
Correlation Clustering with a Fixed Number of Clusters by Ioannis Giotis and Venkatesan Guruswami 
Vol 2, Article 12 (pp 225247)
Matrix Approximation and Projective Clustering via Volume Sampling by Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang 
Vol 2, Article 11 (pp 207224)
Embedding the Ulam metric into ℓ_{1} by Moses Charikar and Robert Krauthgamer 
Vol 2, Article 7 (pp 137146)
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 6590)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua BureshOppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi 
Vol 2, Article 3 (pp 5364)
An Improved Approximation Ratio for the Covering Steiner Problem by Anupam Gupta and Aravind Srinivasan 
Vol 2, Article 2 (pp 1951)
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 119148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot 