Atlas home || Conferences | Abstracts | about Atlas
Host: Fields Institute
Homepage: http://www.fields.utoronto.ca/gtalgorithms.html
Email: hardproblems@fields.utoronto.ca
Organizers: Joseph Cheriyan (University of Waterloo), Michel Goemans (University of Louvain and MIT), David Shmoys (Cornell University)
Description:
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.
Date received: September 30, 1999
© 2008 Atlas Conferences Inc.