A selection of topics for presentations:
- Facility Location Problem:
- Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang, Approximation Algorithms for
Metric Facility Location Problems, SIAM Journal on Computing 36
(2), 411-432, 2006.
- Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi,
and Vijay Vazirani, Greedy
Analyzed using Dual Fitting with Factor-Revealing LP,
Journal of the ACM, 50 (6), pp. 795-824, November 2003.
- M. Sviridenko. An improved approximation algorithm for the
uncapacitated facility location problem. In Proc. of the 9th Integer
Programming and Combinatorial Optimization (IPCO), pages 240-257, 2002.
- F. A. Chudak and D. B. Shmoys. Improved approximation
the uncapacitated facility location problem. SIAM J. Comput., 33(1),
pages 1-25, 2003.
- Jaroslaw Byrka.
An optimal bifactor approximation
algorithm for the metric
uncapacitated facility location problem.
In Proceedings of APPROX 2007
- Approximation for high-connected subgraphs:
- G. Kortsarz and Z. Nutov, Approximating min-cost
connectivity problems, Survey Chapter in handbook on approximation,
a pdf file
- J. Cheriyan, S. Vempala, and A. Vetta, An approximation
algorithm for the minimum-cost
k-vertex connected subgraph, SIAM J. Comput.) 32 (2003) pp.1050-1055, postscript
- J. Cheriyan and A. Vetta, Approximation Algorithms for Network
Design with Metric Costs, to appear in SIDMA (SIAM J. Discr. Math.), postscript
- "Approximating the smallest k-edge connected spanning subgraph
by LP-rounding", H.N. Gabow, M.X. Goemans, E. Tardos and D.P.
SODA 05, pp. 562-571. Complete version: postscript
- G. Kortsarz and Z. Nutov, Approximation Algorithms for
k-node connected subgraphs, via critical graphs, SIAM journal on
Computing, 35(1), 247-257, 2005. postscript
- Bounded degree subgraphs:
- Approximating metrics by tree metrics:
- N. Alon, R. Karp, D. Peleg, D. B. West,
A graph-theoretic game and its application to the k-server problem,
- Y. Bartal,
Probabilistic Approximations of Metric Spaces and its Algorithmic
Applications, FOCS 1996.
- J. Fakcharoenphol, S. Rao and K. Talwar, A tight bound on
approximating arbitrary metrics by tree metrics. STOC 2003.
- M. Elkin, Y. Emek, D. Spielman, S. Teng, Lower Stretch
Spanning Trees, STOC
Arora: Polynomial time approximation schemes for Euclidean TSP and
other Geometric Problems, ournal of the
ACM 45(5) 753-782, 1998. [Postscript
of journal version].
- Sanjeev Arora, Satish Rao, and
Umesh Vazirani. Expander
flows, geometric embeddings, and graph partitionings, STOC 2004
- k-Median Problem:
- Uriel Feige, Robert Krauthgamer:
A polylogarithmic approximation of the minimum bisection. SIAM
Journal on Computing, 31(4): 1090--1118 (2002).
- C. Chekuri, M. Charikar, T. Cheung, Z. Dai, A. Goel, S. Guha, and
Ming Li, Approximation
Algorithms for Directed
, in Journal of Algorithms, 1999, 33: 73-91.
- Naveen Garg, Goran
Konjevod and R. Ravi,
A polylogarithmic approximation algorithm for the group Steiner problem
special issue of
Journal of Algorithms
- Approximation algorithms for directed multicut:
- Approximation algorithms for Buy-at-Bulk:
- B. Awerbuch and Y. Azar, Buy-at-bulk
network design, FOCS 97.
- Adam Meyerson,
Kamesh Munagala, and Serge
Two-Metric Network Design. IEEE
Symposium on Foundations of Computer Science (FOCS) 2000.
- C. Chekuri, S. Khanna, and S. Naor, A
Deterministic Algorithm for the
, short paper in SODA 2001.
Chekuri, M. Hajiaghayi, G. Kortsarz,
Algorithms for Non-Uniform Buy-at-Bulk Network Design problems, In Proceedings of
- D. Karger, R. Motwani, M. Sudan, Approximate Graph Coloring by
Semidefinite Programming, Journal of the ACM, 45(2):
246--265, March 1998. postscript
Hardness of approximation:
- Uriel Feige. A
Threshold of ln n for Approximating Set Cover. Journal of the ACM,
45(4), 634--652, July 1998.
- Hardness of cost-distance and Buy-at-bulk network design:
- Hardness of edge-disjoint paths:
- Hardness of congestion minimization:
- Hardness of Multi-cut and Sparsest cut:
- Lower bound for group Steiner tree and directed Steiner tree:
- Eran Halperin,
Aravind Srinivasan and Nan Wang, Integrality ratio for group Steiner
trees and Directed Steiner trees,
Journal on Computing, 2007.
- Eran Halperin and Robi Krauthgamer, Polylogarithmic
inapproximability, In Proceedings of STOC 2003.
- Irit Dinur, Venkatesan Guruswami, Subhash Khot, A new
multilayered PCP and the hardness of hypergraph vertex cover,
STOC 2003, to appear in SICOMP)
- Håstad result (warning: this is difficult):
- Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy
Kortsarz, Robert Krauthgamer, and Seffi Naor, Asymmetric
k-center is log^*n-hard to Approximate JACM 2(4):538-551, 2005