SCHEDULE

Many of the problems that arise in practical applications of discrete optimization are NP-hard; that is, optimal solutions cannot be computed in polynomial time modulo the P .not.=NP conjecture. Current research is focusing on the design of polynomial - time approximation algorithms for such problems. An algorithm for an optimization problem is said to achieve an approximation guarantee of alpha if it delivers a solution that is guara nteed to be within an alpha factor of optimal on every instance of the problem. Results and methods from combinatorial optimization have come to play a major role in the design of approximation algorithms and in the analysis of the approximation guarantees. One of the widely applicable algorithmic paradigms developed in combinatorial optimization is the primal-dual method. Currently, the best approximation algorithms for several NP - hard problems are based on this method. Furthermore, for many problems, the best known approximation guarantees are achieved by solving a cleverly formulated linear-programming (LP) relaxation, and then using simple heuristics to "round" the optimal LP solution to obtain a near-optimal solution to the instance. Similar methods using semidefinite programming, rather than linear programming, have proved successful too.

Invited speakers and participants include:

• S. Arora, Princeton University
• M. Charikar, Stanford University
• C. Chekuri, Bell Laboratories, Lucent
• F. Chudak, IBM T.J. Watson Research Center
• U. Feige, The Weizmann Institute of Science
• N. Garg, Indian Institute of Technology, New Delhi
• S. Guha, Stanford University
• K. Jain, Georgia Institute of Technology
• D. Karger, Massachusetts Institute of Technology
• H. Karloff, Georgia Institute of Technology
• M. Karpinski, University of Bonn
• S. Khuller, University of Maryland at College Park
• J. Kleinberg, Cornell University
• N. Linial, Hebrew University of Jerusalem
• Y. Rabani, Technion, Israel Institute of Technology
• S. Rao, University of California at Berkeley
• R. Ravi, Carnegie Mellon University
• M. Skutella, CORE, Universite Catholique de Louvain
• M. Sviridenko, Sobolev Institute of Mathematics
• V. Vazirani, Georgia Institute of Technology
• S. Vempala, Massachusetts Institute of Technology
• D. Williamson, IBM T.J. Watson Research Labs
• U. Zwick, Tel Aviv University