 |
SPECIAL YEAR
ON GRAPH THEORY AND COMBINATORIAL OPTIMIZATION
Workshop on Approximation Algorithms for Hard Problems
in Combinatorial Optimization
September 26 - October 1, 1999
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).
|
|
