Atlas home || Conferences | Abstracts | about Atlas
Host: Nassau Inn
Homepage: http://dimacs.rutgers.edu/Workshops/Approx/
Organizers: Sanjeev Arora (Princeton University), Eva Tardos (Cornell University), Luca Trevisan (Columbia University)
Description:
This workshop focuses on the design and analysis approximation algorithms, heuristics that compute solutions whose value is
provably within some fixed factor of the optimal. Although research on approximation algorithms started in 1970s soon after
the discovery of NP-completeness, it has truly blossomed only in the past decade. Amazing progress has ocurred both in our
ability to design approximation algorithms, and in proving limits to approximability. Approximation algorithms have been
designed for many important problems such as balanced cut, network design, Euclidean TSP, facility location, and a number of
scheduling problems. In the process, many simple and broadly-applicable techniques have emerged, such as rounding followed
by dynamic programming, and more recently, the rounding of solutions obtained from linear or semi-definite relaxations,
primal-dual methods, geometric embeddings, and the geometric divide-and-conquer approaches used for Euclidean TSP.
Date received: October 07, 1999
© 2008 Atlas Conferences Inc.