I have moved to the University of Waterloo and am no longer maintaining this
website.
The contact information below is obsolete.
You should be automatically redirected to my new homepage
http://www.math.uwaterloo.ca/~cswamy
in about 5 seconds.
Chaitanya Swamy
Center for the Mathematics of Information
338 Moore Laboratory, MC 136-93
Caltech
1200 E. California Blvd.
Pasadena, CA 91125
(626) 395-1768
cswamy AT ist DOT caltech DOT edu
Hi.
I am a postdoctoral scholar at the Center for
the Mathematics of Information (CMI) at Caltech
and will
be joining the Department
of Combinatorics and Optimization at the University
of Waterloo in September 2006.
I graduated from the Department of Computer
Science at Cornell University in May 2004.
My advisor
was David Shmoys.
For research, I mostly think about algorithms. My research interests include
combinatorial optimization,
approximation algorithms, network design,
stochastic optimization, algorithmic game theory, scheduling,
and online algorithms.
Publications
- The Effectiveness of Lloyd-type Methods for the k-Means Problem
(with Rafail Ostrovsky,
Yuval Rabani and
Leonard Schulman).
Submitted.
- Labeling Hierarchical Taxonomies
(with Yuval Rabani
and Leonard Schulman).
Submitted.
-
Approximation Algorithms for Graph Homomorphism Problems
(with Michael Langberg and
Yuval Rabani).
To appear in Proceedings of APPROX 2006.
ps or pdf.
-
Approximation Algorithms for 2-Stage Stochastic Optimization Problems
(with David Shmoys).
Survey article in ACM SIGACT News, 37(1):33-46, March 2006.
ps or pdf.
Slides (ppt) from a survey talk given at
the Aladdin Workshop
on Flexible Network Design, November 2005.
-
Truthful and Near-optimal Mechanism Design via Linear Programming
(with Ron Lavi).
Proceedings of FOCS 2005, pages 595-604.
A more detailed version ps,
pdf or
conference version ps, pdf.
Slides: Long version (ppt) or a (slightly)
shorter version (ppt).
Presented at FOCS, October 2005; Theory seminars at Caltech, November 2005 and
IBM Yorktown Heights, December 2005.
-
Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization
(with David Shmoys).
Proceedings of FOCS 2005, pages 357-366.
Detailed version ps, pdf
or conference version ps, pdf.
Slides: Short version (ppt).
Presented at FOCS, October 2005; Oberwolfach
Workshop on Combinatorial Optimization, November 2005.
-
The Sample Average Approximation Method for 2-stage Stochastic Optimization
(with David Shmoys).
Unpublished manuscript, 2004.
ps or pdf.
-
Network Design for Information Networks
(with Ara Hayrapetyan and
Éva Tardos).
Proceedings of SODA 2005, pages 933-942.
ps or pdf.
Slides: Short version (ppt).
Presented at the Bertinoro Workshop on Models and Algorithms for Information Networks
(MAIN),
October 2004; INFORMS Annual Meeting (invited talk), November 2005.
-
An Approximation Scheme for Stochastic Linear Programming and its Application to
Stochastic
Integer Programs (with David Shmoys).
Accepted (with revisions) to the Journal of the ACM.
Preliminary version appeared as "Stochastic Optimization is (almost) as Easy as
Deterministic Optimization"
in Proceedings of FOCS 2004, pages 228-237.
Journal version ps, pdf
or conference version ps, pdf.
See also my PhD thesis.
Slides: Long version (ppt) or
short version (ppt).
Presented at Cornell University; CMI Fall 2004 Retreat; 10th International Conference on
Stochastic
Programming (SPX), 2004; FOCS 2004; Dagstuhl
Seminar on Algorithms for Optimization with
Incomplete Information, 2005; Theory
and IEOR seminars at the University of Rome "La Sapienza",
MIT, Brown University, IBM Yorktown Heights, Columbia University.
-
Optimal Power-down Strategies
(with John Augustine and
Sandy Irani).
Proceedings of FOCS 2004, pages 530-539.
Detailed version ps, pdf
or conference version ps, pdf.
Slides: Short version (ppt).
Presented at FOCS, Rome, October 2004.
-
Algorithms for the Data Placement Problem.
Unpublished manuscript, 2004.
ps or pdf.
To be combined with the paper "Approximation Algorithms for Data Placement in Arbitrary Networks"
(Ivan Baev and
Rajmohan Rajaraman, SODA 2001).
-
LP-based Approximation Algorithms for Capacitated Facility Location
(with Retsef Levi and
David Shmoys).
Proceedings of IPCO 2004, pages 206-218.
ps or pdf.
Slides: Short version (ppt).
Presented at IPCO, New York, June 2004.
-
Correlation Clustering: Maximizing Agreements via Semidefinite Programming.
Proceedings of SODA 2004, pages 519-520.
ps or pdf.
Won the Best Student Paper Award.
Slides: Short version (ppt).
Presented at the Theory Seminar at Cornell, November 2003 and at SODA, New Orleans, January 2004.
-
Facility Location with Service Installation Costs
(with David Shmoys and
Retsef Levi).
Proceedings of SODA 2004, pages 1081-1090.
ps or pdf.
Slides: Short version (ppt).
Presented at SODA, New Orleans, January 2004.
-
Fault-Tolerant Facility Location
(with David Shmoys).
Proceedings of SODA 2003, pages 735-736.
Detailed version ps, pdf
or conference version ps, pdf.
Slides: Long version (ppt) or
short version (ppt).
Presented at the Theory Seminar at Cornell, April 2002 and at SODA, Baltimore, January 2003.
-
Primal-Dual Algorithms for Connected Facility Location Problems
(with Amit Kumar).
Algorithmica, 40(4):245-269, 2004.
Special issue devoted to the best papers from APPROX 2002.
Preliminary version in Proceedings of APPROX 2002, pages 256-269.
Detailed version ps, pdf
or conference version ps, pdf.
Slides: Long version (ppt) or a (slightly)
shorter version (ppt).
Presented at the Algorithms Seminar at the
Max-Planck-Institut für Informatik, Saarbrücken, August 2002;
APPROX, Rome, September 2002; Theory Seminar at Cornell, October 2002;
Integrated Logistics Workshop (an ALADDIN PROBE) at Princeton, October 2002.
-
A Randomized Algorithm for Flow Shop Scheduling
(with Naveen Garg and
Sachin Jain).
Proceedings of FSTTCS 1999, pages 213-218.
ps or pdf.
Created November 2004.
Updated June 2006.