Optimization

1. Local versus global properties of metric spaces (S. Arora, L. Lov?sz, I. Newman, Y. Rabani and Y. Rabinovich)
   To appear in Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms , 2006.
   
2. A simple polynomial-time rescaling algorithm for solving linear programs.(John Dunagan)
   Proc. of the 36th ACM Symposium on the Theory of Computing (STOC '04), Chicago, 2004.
   
3. Solving convex programs by random walks. (Dimitris Bertsimas)
   Journal of the ACM (JACM) 51(4), 540--556, 2004.
   Proc. of the 34th ACM Symposium on the Theory of Computing (STOC '02), Montreal, 2002.
   
4. An approximation algorithm for the minimum-cost k-vertex connected subgraph.
   (Joseph Cheriyan, Adrian Vetta)
   SIAM J. Computing, 32(4) (2003), 1050-1055.
   
5. Network design via iterative rounding of setpair relaxations. (Joseph Cheriyan, Adrian Vetta)
   To appear in Combinatorica.
   A preliminary version of the previous two appeared as
   Approximation algorithms for minimum-cost k-connected subgraphs.
   Proc. of the 34th ACM Symposium on the Theory of Computing (STOC '02), Montreal, 2002.
   
6. Flow metrics. (Claudson Bornstein)
   Proc. of the 5th Symposium on Latin American Theoretical Informatics, Cancun, 2002.
   Theoretical Computer Science (special issue for LATIN '02), 321(1), 13--24, 2004.
   
7. On the approximability of the traveling salesman problem. (Christos H. Papadimitriou)
   Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000.
   To appear in Combinatorica.
   
8. On Euclidean embeddings and bandwidth minimization. (John Dunagan)
   Proc. of the 5th Workshop on Randomization and Approximation, Berkeley, 2001.
   
9. Edge covers of setpairs and the iterative rounding method. (Joseph Cheriyan)
   Proc. of Integer Programming and Combinatorial Optimization, Utrecht, 2001.
10. Fences are futile: on relaxations for the linear ordering problem. (Alantha Newman)
    Proc. of Integer Programming and Combinatorial Optimization, Utrecht, 2001.
11. Factor 4/3 approximations for minimum 2-connected subgraphs. (Adrian Vetta)
    Proc. of the 3rd Workshop on Approximation , Saarbrucken, 2000.
    
12. Randomized meta-rounding. (Bob Carr)
    Random Structures and Algorithms, 20(3), (2002), 343-352 (invited).
    Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000.
    
13. On the Held-Karp relaxation for the asymmetric and symmetric TSPs. (Bob Carr)
    Proc. of the 11th ACM-SIAM Symposium on Discrete Algorithms , San Francisco, 2000.
    Mathematical Programming, 100(3), 569--587, 2004.
    
14. Approximating multicast congestion. (Berthold Vocking)
    Proc. of ISAAC, Chennai, 1999.
    
15. A convex relaxation for the Asymmetric TSP. (Mihalis Yannakakis)[two pages only]
    Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999.
    
16. Random Projection: A New Approach to VLSI Layout.
    Proc. of the 39th Foundations of Computer Science (FOCS '98), Palo Alto, 1998.
    
17. Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
    (Avrim Blum, Goran Konjevod and R. Ravi)
    Proc. of the 30th ACM Symposium on the Theory of Computing (STOC '98), Dallas, 1998.
    Theoretical Computer Science, 235 (2000), 25-42 (special issue in honour of Manuel Blum).
    
18. A Constant-Factor Approximation for the k-MST Problem. (Avrim Blum, R. Ravi)
    Proc. 28th ACM Symposium on the Theory of Computing (STOC '96), Philadelphia, 1996.
    J. Computer and System Sciences, 58(1), 101-108 (special issue for STOC '96).
    
19. Improved Approximations for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
    (Baruch Awerbuch, Yossi Azar, Avrim Blum)
    Proc. 27th ACM Symposium on the Theory of Computing (STOC '95), Las Vegas, 1995.
    SIAM J. on Computing, 28(1) 1999.
    
20. A Constant-Factor Approximation for the k-MST Problem in the Plane. (A. Blum, P. Chalasani)
    Proc. 27th ACM Symposium on the Theory of Computing (STOC '95), Las Vegas, 1995.
    A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane
    ( J.S.B. Mitchell, A. Blum, P. Chalasani)
    Siam J. on Computing , 28(3) 1999.
    
21. Improved Approximations for Finding Minimum 2-connected Subgraphs via Better Lower-Bounding Techniques
    (Naveen Garg, Aman Singla)
    Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, Austin, 1993.
22. Vivek Arora, Huzur Saran, Vijay Vazirani and Santosh Vempala,
    ``A Limited-Backtrack Greedy Schema for Approximation Algorithms,''
    Proc. 14th Symposium on the Foundations of Software Technology and Theoretical Computer Science, Madras, 1994.