Bibliography

ABC+99

F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko.
Approximation schemes for minimizing average weighted completion time with release dates.
In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 32-43, 1999.

ARSY99

J. A. Aslam, A. Rasala, C. Stein, and N. Young.
Improved bicriteria existence theorems for scheduling.
In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, pages 846-847, 1999.

CH99

F. Chudak and D. Hochbaum.
A half-integral linear programming relaxation for scheduling precedence constrained jobs on a single machine.
Operations Research Letters, 25:199-204, 1999.

CM99

C. Chekuri and R. Motwani.
Precedence constrained scheduling to minimize weighted completion time on a single machine.
Discrete Applied Mathematics, 98:29-39, 1999.

CMNS01

C. Chekuri, R. Motwani, B. Natarajan, and C. Stein.
Approximation techniques for average completion time scheduling.
SIAM Journal on Computing, 31(1):146-166, 2001.

CPS+96

S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein.
Improved scheduling algorithms for minsum criteria.
In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming, number 1099 in Lecture Notes in Computer Science. Springer, Berlin, 1996.
Proceedings of the 23rd International Colloquium (ICALP'96).

CS97

F. A. Chudak and D. B. Shmoys.
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds.
In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, 1997.

Goe97

M. Goemans.
Improved approximation algorithms for scheduling with release dates.
In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 591-598, 1997.

GQS+99

M. Goemans, M. Queyranne, A. Schulz, M. Skutella, and Y. Wang.
Single machine scheduling with release dates.
Preprint, 1999.

HS01

C. Hepner and C. Stein.
Implementation of a PTAS for scheduling with release dates.
In Proceedings of ALENEX, 2001.

HSSW97

L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein.
Scheduling to minimize average completion time: Off-line and on-line approximation algorithms.
Mathematics of Operations Research, 22:513-544, August 1997.

Kle96

J. M. Kleinberg.
Single-source unsplittable flow.
In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 68-77, October 1996.

KS97

S. G. Kolliopoulos and C. Stein.
Improved approximation algorithms for unsplittable flow problems.
In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 426-436, 1997.

KS98

S. G. Kolliopoulos and C. Stein.
Approximating disjoint-path problems using greedy algorithms and packing integer programs.
In Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization, pages 153-168, 1998.

KS99

S. G. Kolliopoulos and C. Stein.
Experimental evaluation of approximation algorithms for single source unsplittable flow.
In Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization, 1999.

KSW98

David Karger, Cliff Stein, and Joel Wein.
CRC Handbook on Algorithms, chapter Scheduling Algorithms.
CRC Press, 1998.

MQW97

F. Margot, M. Queyranne, and Y. Wang.
Decompositions, network flows and a precendece constrained single machine scheduling problem.
talk by M. Queyranne at IMPS 97, 1997.

MSS96

R. H. Möhring, M. W. Schäffter, and A. S. Schulz.
Scheduling jobs with communication delays: Using infeasible solutions for approximation.
In J. Diaz and M. Serna, editors, Algorithms - ESA'96, volume 1136 of Lecture Notes in Computer Science, pages 76 - 90. Springer, Berlin, 1996.
Proceedings of the 4th Annual European Symposium on Algorithms.

PSW98

C. Phillips, C. Stein, and J. Wein.
Minimizing average completion time in the presence of release dates.
Mathematical Programming, 82:199-223, 1998.

Ras99

April Rasala.
Existence theorems for scheduling to meet two objectives.
Undergraduate Thesis, 1999.
Dartmouth College, Dept. of Computer Science.

RTSU02

A. Rasala, E. Torng, C. Stein, and P. Uthaisombut.
Existence theorems, lower bound and algorithms for scheduling to meet two objectives.
In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, 2002.

Sch95

A.S. Schulz.
Scheduling to minimize total weighted completion time: performance guarantees of lp based heuristics and lower bounds.
Technical Report 474/1995, Technical University of Berlin, 1995.

SRW98

Martin W.P. Savelsbergh, R.N.Uma, and Joel Wein.
An experimental study of LP-based scheduling heuristics.
In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pages 453-461, 1998.

SS97a

A. S. Schulz and M. Skutella.
Random-based scheduling: New approximations and LP lower bounds.
In J. Rolim, editor, Randomization and Approximation Techniques in Computer Science, volume 1269 of LNCS, pages 119 - 133. Springer, Berlin, 1997.
Proceedings of the International Workshop RANDOM'97.

SS97b

A. S. Schulz and M. Skutella.
Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria.
In R. Burkard and G. Woeginger, editors, Algorithms - ESA'97, volume 1284 of LNCS, pages 416 - 429. Springer, Berlin, 1997.
Proceedings of the 5th Annual European Symposium on Algorithms.

SW97

C. Stein and J. Wein.
On the existence of schedules that are near-optimal for both makespan and total weighted completion time.
Operations Research Letters, 21:115-122, 1997.

SW01

C. Stein and D. Wagner.
Approximation algorithms for the minimum bends traveling salesman problem.
In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pages 406-421, 2001.

In addition to these papers, Professor Stein released software package to find minimum cuts in graphs.¹⁵

Professor Stein was a co-author of the second edition of Introduction to Algorithms,¹⁶ the leading textbook in the field.

Subsections

• Contributions
  • Human resources.