David B. ShmoysProfessor PhD UC Berkeley, 1984 |
 |
The primary focus of my research is on the design and analysis of efficient algorithms for discrete optimization problems, and in particular, on approximation algorithms for NP-hard problems.
Computational complexity theory provides a mathematical foundation for the intractability of many computational problems by proving that all NP-complete problems are equally hard. However, in practice, real-world inputs for some NP-hard optimization problems are straightforward to solve, whereas for others, even quite modestly sized inputs are beyond the limits of the most sophisticated methods. Analogously, from a theoretical perspective, for some NP-hard optimization problems it is possible to efficiently compute solutions that are guaranteed to be arbitrarily close to optimal, whereas for others computing even a crude approximation to the optimum is also NP-hard. In fact, the extent to which such approximation algorithms exist for a problem provides a theoretical yardstick for its actual computational difficulty that is surprisingly accurate. Our work was motivated by the fact that certain linear programming relaxations have been shown to provide extremely good lower bounds on typical data. We provided a theoretical understanding of the strength of these bounds by designing algorithms that "round" the fractional solutions to these linear programs to nearby integer solutions without degrading the quality of the solution too much. PhD student F. Chudak and I developed an algorithm for a basic problem in operations research, the uncapacitated facility problem, which is guaranteed to come within a factor of 1+2/e of optimal. Not only is the theoretical performance of the algorithm surprisingly good, but it is more effective in practice than all previously known heuristic procedures for this problem. We have also begun to investigate algorithms for several capacitated versions of this problem, which arise in a much broader range of applications.
University Activities
Committee on Academic Standards, Petitions, and Credits (ASPAC), College of Engineering
Colloquium Committee, Center for Applied Mathematics
Admissions Committee, Computer Science
Professional Activities
Editor-in-Chief: SIAM J. Discrete Mathematics
Editor: SIAM J. Computing, Special Issue of Mathematical Programming B on Applications of Computer Science Techniques to Combinatorial Optimization (in memory of Eugene L. Lawler)
Associate Editor: Mathematics of Operations Research, Mathematical Programming A, J. Scheduling
Program Committee Member: 9th ACM-SIAM Symp. Discrete Algorithms, 6th Integer Programming and Combinatorial Optimization Conf. (IPCO), APPROX '98 (ICALP '98 satellite)
Co-Organizer: Schloss Dagstuhl Workshop on Approximation Algorithms
Lectures
Using coin tosses and linear programming to find good routings and schedules. Invited Lecture. 3rd German-American "Frontiers of Science" Symp., jointly sponsored by the National Academy of Sciences and the German Humboldt Foundation (Munich), June 1997.
Approximation algorithms for facility location problems. Dagstuhl Workshop on Approximation algorithms, Aug. 1997.
___. IBM Watson Research Center, Aug. 1997.
___. MIT Lab for Computer Science, Dec. 1997.
___. Dept. Mathematical Sciences, Johns Hopkins Univ., April 1998.
Approximation algorithms via linear programming. Invited lecture. APPROX '98.
Publications
Approximation algorithms. Proc. National Academy of Sciences 94 (Nov. 1997), 12734-12735 (with A. Schulz and D. Williamson).
Scheduling to minimize the average completion time: offline and online approximation algorithms. Mathematics of Operations Research 22 (1997), 513-544 (with L. Hall, A. Schulz and J. Wein).
Improved bounds on relaxations of a parallel machine scheduling problem. J. Combinatorial Optimization 1 (1998), 413-426 (with C. Phillips, A. Schulz, C. Stein and J. Wein).