Tuesday
Wednesday
Organizers:
Joe Mitchell, SUNY Stony Brook, [email protected]
Pankaj Agarwal, Duke University, [email protected]
Presented under the auspices of the Special Focus on Computational
Geometry and Applications.
****************************************************************
Combinatorial optimization typically deals with problems of maximizing
or minimizing a function of one or more variables subject to a large
number of constraints. In many applications, the underlying
optimization problem involves a constant number of variables and a
large number of constraints that are induced by a given collection of
geometric objects; these problems are referred to as
geometric-optimization problems. Typical examples include facility
location, low-dimensional clustering, network-design, optimal
path-planning, shape-matching, proximity, and statistical-measure
problems. In such cases one expects that faster and simpler algorithms
can be developed by exploiting the geometric nature of the
problem. Much work has been done on geometric-optimization problems
during the last twenty-five years. Many elegant and sophisticated
techniques have been proposed and successfully applied to a wide range
of geometric-optimization problems. Several randomization and
approximation techniques have been proposed. In parallel with the
effort in the geometric algorithms community, the mathematical
programming and combinatorial optimization communities have made
numerous fundamental advances in optimization, both in computation and
in theory, during the last quarter century. Interior-point methods,
polyhedral combinatorics, and semidefinite programming have been
developed as powerful mathematical and computational tools for
optimization, and some of them have been used for geometric problems.