CS 7520 - Approximation Algorithms
List of papers
Most of these papers are available online either through the library
or from the authors' webpages.
-
O(log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems.
A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. Proc. of STOC, 2005.
-
Expander Flows, Geometric Embeddings, and Graph Partitionings.
S. Arora, S. Rao and U. Vazirani.
Proc. of STOC, 2004
-
Minimizing Congestion in General Networks.
H Raecke - FOCS, 2002
-
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
A Gupta, R Ravi, A Sinha - IEEE Symposium on Foundations of Computer Science (FOCS), 2004
-
Maximizing quadratic programs: extending Grothendieck's Inequality.
M Charikar, A Wirth - Proc. 45th FOCS, 2004
-
Proving Integrality Gaps without Knowing the Linear Program.
S Arora, B Bollobas, L Lovasz, I Tourlakis - FOCS, 2002
-
Edge-Disjoint Paths in Planar Graphs.
C Chekuri, S Khanna, FB Shepherd - on Foundations of Computer Science (FOCS'04)
-
An approximate max-Steiner-tree-packing min-Steiner-cut theorem.
LC Lau - 45th IEEE Symposium on Foundations of Computer Science FOCS 2004
-
Simpler and better approximation algorithms for network design.
A Gupta, A Kumar, T Roughgarden - STOC, 2003
-
Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows.
N Bansal, A Blum, S Chawla, A Meyerson, CA Los - 36th ACM Symposium on Theory of Computing (STOC), 2004
- A tight bound on approximating arbitrary metrics by tree metrics.
J Fakcharoenphol, S Rao, K Talwar - STOC, 2003
-
Primal-dual meets local search: approximating MST's with nonuniform degree bounds.
J Koenemann, R Ravi - STOC, 2003
-
Approximate counting of inversions in a data stream.
M Ajtai, TS Jayram, R Kumar, D Sivakumar - STOC, 2002
-
Similarity estimation techniques from rounding algorithms.
MS Charikar - STOC, 2002
-
Aggregating Inconsistent Information: Ranking and Clustering.
N Ailon, M Charikar, A Newman - Proceedings of the thirty-seventh annual ACM STOC, 2005
-
An improved approximation algorithm for the 0-extension problem.
J Fakcharoenphol, C Harrelson, S Rao, K Talwar - SODA, 2003
Contact Information:
webmaster@cc.gatech.edu
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280
Last Modified: Nov. 26, 1997