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 Held-Karp 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 3-CUT 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. 96-115.
- Improved
Approximation Algorithms for Maximum Cut and Satisfiability Problems ,
with Michel Goemans, JACM, 42:1115-1145, 1995. Preliminary version
appeared in STOC '94, pp. 422-431.
- New
3/4-Approximation Algorithms for the Maximum Satisfiability Problem , with
Michel Goemans, SIAM Journal on Discrete Mathematics , 7:656-666, 1994.
Preliminary
version appeared in IPCO '93, pp. 313-321.
Network design problems
- Iterative
rounding 2-approximation algorithms for minimum-cost vertex connectivity
problems, with Lisa Fleischer and Kamal Jain. Preliminary version appeared
in FOCS '01.
- Approximate
k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean
relaxation, with Fabian Chudak and Tim Roughgarden. Preliminary version
appeared in IPCO 2001, pp. 66-70.
- A
primal-dual schema based approximation algorithm for the element connectivity
problem, with Kamal Jain, Ion Mandoiu, and Vijay Vazirani. Preliminary
version appeared in SODA '99, pp. 484-489.
- 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. 223-232.
- A Primal-Dual Approximation Algorithm for Generalized Steiner Network
Problems, with Michel Goemans, Milena Mihail, and Vijay Vazirani,
Combinatorica, 15:435-454, December 1995. Preliminary version appeared
in STOC '93, pp. 708-717.
- An Efficient Approximation Algorithm for the Survivable Network Design
Problem, with Michel Goemans and Harold Gabow. Mathematical
Programming, 82:13-40, 1998. Preliminary version appeared in IPCO
'93, pp. 57-74.
- Computational Experience with an Approximation Algorithm on Large-Scale
Euclidean Matching Instances, with Michel Goemans, INFORMS Journal on
Computing, 8:29-40, Winter 1996. Preliminary version appeared in SODA '94,
pp. 355-364.
- A
General Approximation Technique for Constrained Forest Problems, with
Michel Goemans, SIAM Journal on Computing, 24:296-317, April 1995.
Preliminary version appeared in SODA '92, pp. 307-316.
Scheduling
- Two-dimensional
Gantt charts and a scheduling algorithm of Lawler , with Michel Goemans.
SIAM Journal on Discrete Mathematics 13:281-294, 2000.
- A
1.47-approximation algorithm for a preemptive single-machine scheduling
problem , with Michel Goemans and Joel Wein. Operations Research
Letters, 26:149-154, 2000.
- Short
Shop Schedules, with Leslie Hall, Han Hoogeveen, Cor Hurkens, Jan Karel
Lenstra, Sergey Sevastjanov, and David Shmoys. Operations Research, 45:
288-294, 1997.
- Scheduling Parallel Machines On-line, with David Shmoys and Joel Wein,
SIAM Journal on Computing, 24:1313-1331, 1995. Preliminary version
appeared in FOCS '91, pp. 131-140.
Feedback vertex set problems
Miscellaneous
- The
approximability of constraint satisfaction, with Sanjeev Khanna and Madhu
Sudan. SIAM Journal on Computing 30:1863-1920, 2001.
- Gadgets,
Approximation, and Linear Programming, with Luca Trevisan, Greg Sorkin,
and Madhu Sudan. SIAM Journal on Computing 29:2074-2097, 2000.
- Node-Disjoint
Paths on the Mesh and a New Trade-Off in VLSI Layout , with Alok Aggarwal
and Jon Kleinberg. SIAM Journal on Computing 29:1321-1333, 2000.
- Adversarial Queueing Theory, with Allan Borodin, Jon Kleinberg, Prabhakar
Raghavan, and Madhu Sudan. JACM 48:13-38, 2001.
- On the Number of Small Cuts in a Graph, with Monika Rauch Henzinger.
Information Processing Letters, 59:41-44, 1996.
Course Notes
|
Vita
Courses
Research
Selected Publications
DPW Home
Cornell ORIE
Cornell CIS
|