This material is presented to ensure timely dissemination of
scholarly and technical work. Copyright and all rights therein are
retained by authors or by other copyright holders. All persons
copying this information are expected to adhere to the terms and
constraints invoked by each author's copyright. In most cases,
these works may not be reposted without the explicit permission of
the copyright holder.
Books
Recent papers
Theses
 On the Design of Approximation Algorithms for a Class of Graph Problems,
PhD thesis, MIT Computer Science, September 1993.
 Analysis of the HeldKarp Heuristic for the Traveling Salesman Problem,
Master's thesis, MIT Computer Science, June 1990. [PDF
2.0MB]
Maximum cut and satisfiability problems
 Approximation
algorithms for MAX 3CUT and other problems via complex semidefinite
programming, with Michel Goemans. Preliminary version appeared in STOC
'01.
 Improved
approximation algorithms for MAX SAT, with Takao Asano. Appeared in
SODA '00, pp. 96115.
 Improved
Approximation Algorithms for Maximum Cut and Satisfiability Problems ,
with Michel Goemans, JACM, 42:11151145, 1995. Preliminary version
appeared in STOC '94, pp. 422431.
 New
3/4Approximation Algorithms for the Maximum Satisfiability Problem , with
Michel Goemans, SIAM Journal on Discrete Mathematics , 7:656666, 1994.
Preliminary
version appeared in IPCO '93, pp. 313321.
Network design problems
 Iterative
rounding 2approximation algorithms for minimumcost vertex connectivity
problems, with Lisa Fleischer and Kamal Jain. Preliminary version appeared
in FOCS '01.
 Approximate
kMSTs and kSteiner trees via the primaldual method and Lagrangean
relaxation, with Fabian Chudak and Tim Roughgarden. Preliminary version
appeared in IPCO 2001, pp. 6670.
 A
primaldual schema based approximation algorithm for the element connectivity
problem, with Kamal Jain, Ion Mandoiu, and Vijay Vazirani. Preliminary
version appeared in SODA '99, pp. 484489.
 Improved
approximation algorithms for capacitated facility location problems, with
Fabian Chudak. Preliminary version appeared in IPCO '99.
 Improved Approximation Algorithms for Network Design Problems, with Michel
Goemans, Andrew Goldberg, Serge Plotkin, David Shmoys, Eva Tardos. Appeared in
SODA '94, pp. 223232.
 A PrimalDual Approximation Algorithm for Generalized Steiner Network
Problems, with Michel Goemans, Milena Mihail, and Vijay Vazirani,
Combinatorica, 15:435454, December 1995. Preliminary version appeared
in STOC '93, pp. 708717.
 An Efficient Approximation Algorithm for the Survivable Network Design
Problem, with Michel Goemans and Harold Gabow. Mathematical
Programming, 82:1340, 1998. Preliminary version appeared in IPCO
'93, pp. 5774.
 Computational Experience with an Approximation Algorithm on LargeScale
Euclidean Matching Instances, with Michel Goemans, INFORMS Journal on
Computing, 8:2940, Winter 1996. Preliminary version appeared in SODA '94,
pp. 355364.
 A
General Approximation Technique for Constrained Forest Problems, with
Michel Goemans, SIAM Journal on Computing, 24:296317, April 1995.
Preliminary version appeared in SODA '92, pp. 307316.
Scheduling
 Twodimensional
Gantt charts and a scheduling algorithm of Lawler , with Michel Goemans.
SIAM Journal on Discrete Mathematics 13:281294, 2000.
 A
1.47approximation algorithm for a preemptive singlemachine scheduling
problem , with Michel Goemans and Joel Wein. Operations Research
Letters, 26:149154, 2000.
 Short
Shop Schedules, with Leslie Hall, Han Hoogeveen, Cor Hurkens, Jan Karel
Lenstra, Sergey Sevastjanov, and David Shmoys. Operations Research, 45:
288294, 1997.
 Scheduling Parallel Machines Online, with David Shmoys and Joel Wein,
SIAM Journal on Computing, 24:13131331, 1995. Preliminary version
appeared in FOCS '91, pp. 131140.
Feedback vertex set problems
Miscellaneous
 The
approximability of constraint satisfaction, with Sanjeev Khanna and Madhu
Sudan. SIAM Journal on Computing 30:18631920, 2001.
 Gadgets,
Approximation, and Linear Programming, with Luca Trevisan, Greg Sorkin,
and Madhu Sudan. SIAM Journal on Computing 29:20742097, 2000.
 NodeDisjoint
Paths on the Mesh and a New TradeOff in VLSI Layout , with Alok Aggarwal
and Jon Kleinberg. SIAM Journal on Computing 29:13211333, 2000.
 Adversarial Queueing Theory, with Allan Borodin, Jon Kleinberg, Prabhakar
Raghavan, and Madhu Sudan. JACM 48:1338, 2001.
 On the Number of Small Cuts in a Graph, with Monika Rauch Henzinger.
Information Processing Letters, 59:4144, 1996.
Course Notes

Vita
Courses
Research
Selected Publications
DPW Home
Cornell ORIE
Cornell CIS
