THEMATIC PROGRAMS

March 28, 2024
SPECIAL YEAR ON GRAPH THEORY AND COMBINATORIAL OPTIMIZATION

Workshop on Approximation Algorithms for Hard Problems in Combinatorial Optimization
September 26 - October 1, 1999

SCHEDULE

Organizing Committee

Joseph Cheriyan, University of Waterloo
Michel Goemans, University of Louvain and MIT
David Shmoys, Cornell University

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

This workshop is partly supported by a grant from the U.S. National Science Foundation (International Programs).