DIMACS Workshop on Geometric Optimization
May 19 - 21, 2003
DIMACS Center, CoRE Building, Rutgers University
Presented under the auspices of the
Special Focus on Computational Geometry and Applications.
- Joe Mitchell, SUNY Stony Brook, firstname.lastname@example.org
- Pankaj Agarwal, Duke University, email@example.com
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.
Scope and Format:
This workshop aims to bring together people from different
research communities interested in geometric-optimization problems.
The goal is to discuss various techniques developed for geometric
optimization and their applications, to identify key research issues
that need to be addressed, and to help establish relationships which
can be used to strengthen and foster collaboration across the
Next: Call for Participation
Contacting the Center
Document last modified on January 23, 2003.