Some of Cliff Stein's Papers

Some Recent Papers. (Links are under construction.)

Bogdan Caprita, Jason Nieh, Clifford Stein: Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling. PODC 2006: 72-81 2005
Robert L. Scot Drysdale, Clifford Stein, David P. Wagner: An O(n5/2log n) Algorithm for the Rectilinear Minimum Link-Distance Problem. CCCG 2005: 97-100
G. Iyengar, David J. Phillips, Clifford Stein: Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring. IPCO 2005: 152-166
J.Feldman, Clifford Stein: LP decoding achieves capacity. SODA 2005: 460-469
Fei Li, Jay Sethuraman, Clifford Stein: An optimal online algorithm for packet scheduling with agreeable deadlines. SODA 2005: 801-802
Bogdan Caprita, Wong Chun Chan, Jason Nieh, Clifford Stein, Haoqiang Zheng: Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems. USENIX Annual Technical Conference, General Track 2005: 337-352
Eyjolfur Asgeirsson, Clifford Stein: Vertex Cover Approximations: Experiments and Observations. WEA 2005: 545-557
Eyjolfur Asgeirsson, Jonathan W. Berry, Cynthia A. Phillips, David J. Phillips, Clifford Stein, Joel Wein: Scheduling an Industrial Production Facility. IPCO 2004: 116-131
David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young: Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. Math. Oper. Res. 29(3): 436-461 (2004)
Stavros G. Kolliopoulos, Clifford Stein: Approximating disjoint-path problems using packing integer programs. Math. Program. 99(1): 63-87 (2004)
David M. Mount, Clifford Stein: Algorithm Engineering and Experiments, 4th International Workshop, ALENEX 2002, San Francicsco, CA, USA, January 4-5, 2002, Revised Papers Springer 2002 54 April Rasala, Clifford Stein, Eric Torng, Patchrawat Uthaisombut: Existence theorems, lower bounds and algorithms for scheduling to meet two objectives. SODA 2002: 723-731
Clint Hepner, Clifford Stein: Minimizing Makespan for the Lazy Bureaucrat Problem. SWAT 2002: 40-50
nthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein: Optimal Time-Critical Scheduling via Resource Augmentation. Algorithmica 32(2): 163-200 (2002)
Javed A. Aslam, April Rasala, Clifford Stein, Neal E. Young: Improved Bicriteria Existence Theorems for Scheduling CoRR cs.DS/0205008: (2002)
David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young: Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut CoRR cs.DS/0205051: (2002)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, Second Edition The MIT Press and McGraw-Hill Book Company 2001
Clint Hepner, Clifford Stein: Implementation of a PTAS for Scheduling with Release Dates. ALENEX 2001: 202-215
Rong Xie, Daniela Rus, Clifford Stein: Scheduling multi-task multi-agent systems. Agents 2001: 159-160
Clifford Stein, David P. Wagner: Approximation Algorithms for the Minimum Bends Traveling Salesman Problem. IPCO 2001: 406-422
Clifford Stein: Simultaneously optimizing two scheduling objectives. IPDPS 2001: 198
Rong Xie, Daniela Rus, Clifford Stein: Scheduling Multi-task Agents. Mobile Agents 2001: 260-276
Christopher Bailey-Kellogg, John J. Kelley, Clifford Stein, Bruce Randall Donald: Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling. Journal of Computational Biology 8(1): 19-36 (2001)
Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein: Approximation Techniques for Average Completion Time Scheduling. SIAM J. Comput. 31(1): 146-166 (2001)
Stavros G. Kolliopoulos, Clifford Stein: Approximation Algorithms for Single-Source Unsplittable Flow. SIAM J. Comput. 31(3): 919-946 (2001)

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

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.

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.