About the Summer School

The 2nd Summer School on Integer Programming and Combinatorial Optimization will prelude IPCO IX. The summer school will be held on MIT campus on May 25-26, 2002. Advanced Ph.D. students, postdocs, junior researchers, and others interested in participating can now officially register for this event. For the schedule of activities, please consult the program page.

The idea of a summer school immediately preceding the IPCO meeting was introduced at the occasion of IPCO VIII in Utrecht. It intends to facilitate the participation of young researchers in the joint events, even if an IPCO submission is not made.

Lectures

Dimitris Bertsimas

Operations Research Group, Sloan School of Management, M.I.T.

Robust Discrete Optimization

We propose an approach to address data uncertainty for discrete optimization problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows to control the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on n variables, then we solve the robust counterpart by solving n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0-1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. Moreover, we show that the robust counterpart of an NP-hard $\alpha$-approximable 0-1 discrete optimization problem, remains $\alpha$-approximable.

(Based on joint work with Melvyn Sim, MIT.)

Santosh Vempala

Department of Mathematics, School of Science, M.I.T.

Set-Pair Formulations for Network Design

The first lecture will be on integer programs for network design based on set-pair constraints and associated exact results for special cases (mostly from a paper by Frank and Jordan). The second lecture will be about linear programming relaxations, their structure, and their application to approximation algorithms for the general case.

David Karger

Department of Electrical Engineering and Computer Science, School of Engineering, M.I.T.

Randomized Algorithms for Cut and Flow Problems

Randomization has become a pervasive technique in combinatorial optimization. Randomization has been used to develop algorithms that are faster, simpler, and/or better-performing than previous deterministic algorithms. I will survey some applications of randomization to cut and flow problems in undirected graphs. Our work uses four important randomization techniques:

Random Selection,: which lets us easily choose a "typical" element of a set, avoiding rare "bad" elements;
Random Sampling,: which provides a quick way to build a small, representative subproblem of a larger problem for quick analysis;
Randomized Rounding,: which lets us transform fractional problem solutions into integral ones; and
Monte Carlo Simulation,: which lets us estimate the probabilities of interesting events.

We apply these techniques to various optimization problems on undirected graphs. Among the graph problems we address are finding (or approximating) a maximum flow, determining the connectivity (minimum cut) of a graph, network design, and estimating the reliability (disconnection probability) of a network with random edge failures. We will attempt to cover material sufficient that demonstrates all four of the techniques listed above. We will begin by presenting a simple minimum cut algorithm [KS96] that demonstrates the power of random selection while laying the groundwork for several other techniques we will use later. While the best deterministic bound for minimum cuts is roughly $O(mn)$ on an $m$-edge, $n$-vertex graph, this randomized algorithm runs in roughly $O(n^2)$ time. The minimum cut algorithm extends to some combinatorial and algorithmic results on near-minimum cuts; applying these ideas to some Monte Carlo simulation methods yields a fully polynomial randomized approximation scheme for the problem of estimating the failure (disconnection) probability of a network suffering random edge failures [Kar99b]. Although the reliability problem is $NP$-complete, our algorithm produces an estimate that is accurate to within an arbitrary relative error of $(1+-\epsilon)$ in time polynomial in $n$ and $1/\epsilon$. Another application of these results is to show good performance for a class of maximum flow approximation algorithms based on random sampling [Kar99a, BK96]. By accepting a flow which is merely approximately maximum, we are able to solve flow problems substantially faster than the best known exact bounds. In a separate application, we give randomized rounding algorithms for network design problems that aim to build a network of minimum cost satisfying certain connectivity properties. By developing techniques for "repairing" our approximate solutions, we can also solve certain problems exactly. In one application [Kar00], we give an algorithm for finding a minimum cut in essentially linear ($O(m\log^3 m)$) time. We also develop an exact maximum flow algorithm [KL02] based on augmenting paths that improves on the best know bounds for finding flow in graphs with unit capacity edges-instead of the classical $O(n^3)$ bound, we achieve a bound of $O(n^{2})$. Some of this work is joint with András A. Benczúr and Matt Levine. While we will not be able to detail all these results, we will survey as many as possible while diving deeply into a few results to give a sense of the techniques. Depending on time, we will also attempt to touch upon related work [Kar98, KKT95, KM97, CGK+97, AKK99, BK00].

References

[AKK99]: Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58:193-210, 1999.
[BK96]: András A. Benczúr and David R. Karger. Approximate s-t min-cuts in $\tilde O(n^2)$ time. In Miller [Mil96], pages 47-55.
[BK00]: András A. Benczúr and David R. Karger. Augmenting undirected edge connectivity in $\tilde O(n^2)$ time. Journal of Algorithms, 37:2-36, 2000.
[CGK+97]: Chandra C. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein. Experimental study of minimum cut algorithms. In Saks [Sak97], pages 324-333.
[Kar98]: David R. Karger. Random sampling and greedy sparsification in matroid optimization problems. B, 82(1-2):41-81, June 1998. A preliminary version appeared in Proceedings of the 34th Annual Symposium on the Foundations of Computer Science.
[Kar99a]: David R. Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2):383-413, May 1999. A preliminary version appeared in Proceedings of the 26th ACM Symposium on Theory of Computing.
[Kar99b]: David R. Karger. A randomized fully polynomial approximation scheme for the all terminal network reliability problem. SIAM Journal on Computing, 29(2):492-514, 1999. A preliminary version appeared in Proceedings of the 27th ACM Symposium on Theory of Computing. A corrected version was published in SIAM Review.
[Kar00]: David R. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46-76, January 2000. A preliminary version appeared in Proceedings of the 28th ACM Symposium on Theory of Computing.
[KKT95]: David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2):321-328, March 1995.
[KL02]: David R. Karger and Matthew S. Levine. Random sampling from residual graphs. In Proceedings of the 33th ACM Symposium on Theory of Computing. ACM, ACM Press, May 2002. To appear.
[KM97]: David R. Karger and Rajeev Motwani. Derandomization through approximation: An NC algorithm for minimum cuts. SIAM Journal on Computing, 26(1):255-272, January 1997. A preliminary version appeared in Proceedings of the 25th ACM Symposium on Theory of Computing.
[KS96]: David R. Karger and Cliff Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, July 1996. Preliminary portions appeared in SODA 1992 and STOC 1993.
[KT97]: David R. Karger and Ray P. Tai. Implementing a fully polynomial time approximation scheme for all terminal network reliability. In Saks [Sak97], pages 334-343.
[Mil96]: Gary Miller, editor. Proceedings of the 28th ACM Symposium on Theory of Computing. ACM, ACM Press, May 1996.
[Sak97]: Michael Saks, editor. Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, January 1997.

Speakers

Dimitris Bertsimas

Dimitris Bertsimas is currently the Boeing Professor of Operations Research at the Sloan School of Management and the Operations Research Center at the Massachusetts Institute of Technology. He has received a BS in Electrical Engineering and Computer Science at the National Technical University of Athens, Greece in 1985, a MS in Operations Research at MIT in 1987, and a Ph.D. in Applied Mathematics and Operations Research at MIT in 1988. Since 1988, he has been with MIT's Sloan School of Management.

His main research interests include discrete optimization, stochastic and dynamic optimization, analysis and control of stochastic systems, computational statistics and applications of Operations Research in finance and e-commerce. He has published widely and he is currently the area editor of Operations Research in Financial Engineering. He has co-authored graduate level textbooks "Introduction to Linear Optimization" (with John Tsitsiklis, Athena Scientific, 1997), and "Data, Models, and Decisions: The Fundamentals of Management Science" (with Robert Freund, Southwestern College Publishing, 2000).

His awards include the Erlang prize (1996), the SIAM prize in optimization (1996), the Bodossaki prize (1998), being a finalist for the Edelman award (1998), the Presidential Young Investigator award (1991-1996), and the Nicholson prize (1988).

Santosh Vempala

Santosh Vempala is an Assistant Professor of Mathematics and a member of the Laboratory for Computer Science as well as a member of the Operations Research Center at MIT. He got his PhD at Carnegie Mellon in 1997. He was Miller fellow at Berkeley during the year 1998-1999 and has been at MIT since. His research interests are in geometry, randomness and combinatorics, especially in the context of polynomial-time algorithms.

David Karger

David Karger (A.B. in Computer Science, 1989, Harvard University, Ph.D., 1994, in Computer Science, Stanford University) is the Harold E. Edgerton Associate Professor of Computer Science and a member of the Laboratory for Computer Science and of the Operations Research Center at the Massachusetts Institute of Technology. His research interests include algorithms and information retrieval. Professor Karger's work in algorithms has focused on applications of randomization to network optimization problems. His dissertation on the topic was awarded the ACM 1994 Doctoral Dissertation Award and the MPS 1997 Tucker Prize. He has published more than 30 technical articles and two book chapters and has served on program committees for the Symposium on Discrete Algorithms and the Symposium on the Foundations of Computer Science. He recently participated in the founding of Akamai technologies, a company that grew out of a research project he co-led. Professor Karger's work on information retrieval includes the co-development of the Scatter/Gather information retrieval system at Xerox PARC, which suggested several novel approaches for efficiently retrieving information from massive corpora and presenting it effectively to users. He has received two patents related to his work on this project.

Back to the IPCO 2002 Conference home page.

Comments and questions to ipco2002@mit.edu. Page maintained by Nicolas Stier. Last updated Tue May 28 00:13:09 EDT 2002.