|
Volume 4, Article 9 (pages 191-193)
[COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem by Viswanath Nagarajan |
|
Volume 4, Article 5 (pages 111-128)
Approximation Algorithms for Unique Games by Luca Trevisan |
|
Volume 4, Article 2 (pages 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 |
|
Volume 4, Article 1 (pages 1-20)
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall |
|
Volume 3, Article 10 (pages 197-209)
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem by Chandra Chekuri and Martin Pál |
■
|
|
Volume 3, Article 9 (pages 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing by Maria-Florina Balcan and Avrim Blum |
|
Volume 3, Article 6 (pages 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman |
|
Volume 3, Article 3 (pages 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, and Amnon Ta-Shma |
|
Volume 2, Article 13 (pages 249-266)
Correlation Clustering with a Fixed Number of Clusters by Ioannis Giotis and Venkatesan Guruswami |
|
Volume 2, Article 12 (pages 225-247)
Matrix Approximation and Projective Clustering via Volume Sampling by Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang |
|
Volume 2, Article 11 (pages 207-224)
Embedding the Ulam metric into ℓ1 by Moses Charikar and Robert Krauthgamer |
|
Volume 2, Article 7 (pages 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd |
|
Volume 2, Article 4 (pages 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi |
|
Volume 2, Article 3 (pages 53-64)
An Improved Approximation Ratio for the Covering Steiner Problem by Anupam Gupta and Aravind Srinivasan |
|
Volume 1, Article 7 (pages 119-148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot |