Cliff Stein, Columbia University in the City of New York, USA

Hard Combinatorial Problems: Engineering
We will discuss progress on two different combinatorial problems. First we will describe a series of results on scheduling non-preemptively to minimize minimum sum objectives. Through these results, we will study various techniques in approximation algorithms including, linear-programming relaxations, rounding, on-line algorithms, approximation schemes and alternative metrics for analysis. The second set of results we will study will be on solving packing and covering linear programs. These programs model a wide range of combinatorial optimization problems, and we will give a series of efficient algorithms for these problems, discuss applications, and also discuss some experimental studies.

References
Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko: Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS 1999: 32-44  

Daniel Bienstock, Garud Iyengar: Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations. SIAM J. Comput. 35(4): 825-854 (2006).

Daniel Bienstock: epsilon-Approximate linear programs: new bounds and computation. SODA 2000: 1-2

Cindy Phillips, Cliff Stein and Joel Wein, Minimizing Average Completion Time in the Presence of Release Dates Mathematical Programming B, 82, 1998.

Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber and Clifford Stein Non-preemptive min-sum scheduling with resource augmentation.

Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein: Approximation Techniques for Average Completion Time Scheduling. SIAM J. Comput. 31(1): 146-166 (2001).

Naveen Garg, Jochen Könemann: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. FOCS 1998: 300-309.

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, 1997, 513-544.

Serge .A. Plotkin, D.B. Shmoys, E. Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research 20, 1995.