Some of Cliff Stein's Papers

If a paper you want does not appear here, please email me

Topics

Scheduling

* Improved Bicriteria Existence Theorems for Scheduling Problems

with J. Aslam, A. Rasala and N. Young. In SODA 99.

* Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

with F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, M. Sviridenko. In FOCS 99.

* Scheduling Algorithms

with David Karger and Joel Wein, a chapter written for the CRC Handbook on Algorithms, 1997.

* Optimal Time Critical Scheduling Via Resource Augmentation

with Cindy Phillips, Eric Torng and Joel Wein, 1997. To appear in Algorithm.s A preliminary version appeared in STOC 97.

* Approximation Techniques for Average Completion Time Scheduling

with C. Chekuri, R. Motwani and B. Natarajan. To appear in SIAM J. Computing. Initial version appeared in Proceedings of SODA '97.

* On the Existence of Schedules that are Near-Optimal for both Makespan and Total Weighted Completion Time

with Joel Wein. In OR Letters, 21, 1997.

* Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem

with Soumen Chakrabarti, Cindy Phillips, Andreas Schulz, David Shmoys and Joel Wein. In Journal of Combinatorial Optimzation, 1, 1998.

* Improved Scheduling Algorithms for Minsum Criteria

with Soumen Chakrabarti, Cindy Phillips, Andreas Schulz, David Shmoys and Joel Wein, 1995. In Proceedings of ICALP '96.

* Minimizing Average Completion Time in the Presence of Release Dates

with Cindy Phillips and Joel Wein, 1995. In Mathematical Programming B, 82, 1998. A Preliminary version appeared in WADS '95.

* Job Scheduling in Rings

with Perry Fizzano, David Karger and Joel Wein. In Journal of Parallel and Distributed Computation, 34:2, 1997. A preliminary version appeared in SPAA '94.

* Task Scheduling in Networks

with Cindy Phillips and Joel Wein, 1995. In SIAM Journal on Discrete Mathematics, 10:4, 1997.. (Preliminary version appeared in SWAT '94)

* Improved Approximation Algorithms for Shop Scheduling Problems

with David Shmoys and Joel Wein, SIAM J. Computing, 23, pp. 617-632, 1994. (Preliminary version appeared in SODA 91)

Multicommodity Flow

* An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow

with A. Goldberg, J. Oldham, and S. Plotkin. In IPCO 98.

* Experimental evaluation of approximation algorithms for single-source unsplittable flow

with S. Kolliopoulos. In IPCO 99.

* Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs

with Stavros Kolliopoulos. In Proceedings of IPCO 98.

* Improved Approximation Algorithms for Unsplittable Flow Problems

with Stavros Kolliopoulos. To appear in SIAM J. Computing. Initial version appeared in Proceedings of FOCS 97.

* A description of a recent implementation of a combinatorial minimum cost multicommodity flow algorithm, done jointly with Andrew Goldberg, Jeffrey Oldham and Serge Plotkin can be found here

* Implementation of a Combinatorial Multicommodity Flow Algorithm,

with Tishya Leong and Peter Shor. In DIMACS Series in Discrete Mathenatics and Theoretical Computer Science: The First DIMACS IMplementation Challenge: Network Flows and Matchings, D. Johnson aand C. McGoech, ed. , 1993

* Fast Approximation Algorithms for Multicommodity Flow Problems

with Tom Leighton, Fillia Makedon, Serge Plotkin, Eva Tardos, and Spyros Tragoudas, Journal of Computer and System Sciences, 50, 228-243, 1995. Preliminary version appeared in STOC '91

* Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts

with Philip Klein, Serge Plotkin and Eva Tardos. SIAM J. Computing, 23, pp. 466-487, 1994. (Preliminary version appeared in STOC '90)

Minimum Cut Problem

* MINIMUM CUT IMPLEMENTATION PAPER. A long (135 pages) preliminary version of Experimental Study of Minimum Cut Algorithms

with Chandra Chekuri, Andrew Goldberg, David Karger and Matthew Levine, 1996 can be found here. Comments are welcome. You can also find another (long) version of this work as Matt Levine's masters thesis at MIT. The version (10 pages) which appeared in the proceedings of SODA97 can be found here.

* A New Approach to the Minimum Cut Problem

with David Karger. JACM, 43:4, pp. 601-640, 1996. Preliminary Version appeared in STOC 93.

Network and Graph Algorithms

* A New Approach to Clusting

with Javed Asalam and Alain Leblanc. In Proceedings of WAE 00.

* Better Rounding Algorithms for a Geometric Embedding Relaxation of Minimum Multiway Cut

with D. Karger, P. Klein, M. Thorup, and N. Young. In STOC 99.

* Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs

with Stavros Kolliopoulos. In Proceedings of IPCO 98.

* Improved Approximation Algorithms for Unsplittable Flow Problems

with Stavros Kolliopoulos. In Proceedings of FOCS 97.

* Finding Real-Valued Single-Source Shortest Paths in o(n^3) Expected Time

with Stavros Kolliopoulos. To appear in Journal of Algorithms. Preliminary version appeared in proceedings of IPCO 96.

* Long Tours and Short Superstrings

with Rao Kosaraju and James Park. In Proceedings of 35th Annual IEEE Symposium on the Foundations of Computer Science, Nov. 1994, pp. 166-177.

* A New Approach to the Minimum Cut Problem

with David Karger. JACM, 43:4, pp. 601-640, 1996.

* Improved Algorithms for Bipartite Network Flow

with Ravi Ahuja, Jim Orlin and Bob Tarjan. In SIAM Journal on Computing, 23:5, pp. 906-933, 1994.

* Parallel Algorithms for the Assignment and Minimum-Cost Flow Problems

with Jim Orlin. In Operations Research Letters, 14, pp. 181-186, 1993.

* Approximating the Minimum-Cost Maximum Flow is P-Complete

with Joel Wein. In Information Processing Letters, 42, pp. 315-319, 1992.

* A Parallel Algorithm for Approximating the Minimum Cycle Cover

with Philip Klein. In Algorithmica, 9, pp. 23-31, 1993.

* A Parallel Algorithm for Eliminating Cycles in Undirected Graphs

with Philip Klein. In Information Processing Letters, 34:6, pp. 307-312, 1990.

Biology and Related Papers

* Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling

with C. Bailey-Kelllog, B. Donald, and J. Kelley. To appear in Journal of Computational Biology. A preliminary version appeared in ISMB, 2000.

* A 2 2/3 Approximation Algorithm for the Shortest Superstring Problem

with Chris Armen. In Discrete Applied Mathematics, 88, 1998. Preliminary version appeared in Proceedings of Combinatorial Pattern Matching, 1996.

* Short Superstrings and the Structure of Overlapping Strings

with Chris Armen. In Journal of Computational Biology, 2, pp. 307-333, 1995.

* Improved Length Bounds for the Shortest Superstring Problem

with Chris Armen. In Proceedings of WADS 1995.

PhD and MS Theses

* PhD Thesis Approximation Algorithms for Multicommodity Flow and Shop Scheduling Problems

. MIT, 1992

* MS Thesis Using Cycles and Scaling in Parallel Algorithms

MIT, 1989.