DIMACS Workshop on Geometric Optimization

May 19 - 21, 2003
DIMACS Center, CoRE Building, Rutgers University

Organizers:
Joe Mitchell, SUNY Stony Brook, jsbm@ams.sunysb.edu
Pankaj Agarwal, Duke University, pankaj@cs.duke.edu
Presented under the auspices of the Special Focus on Computational Geometry and Applications.

Rationale:

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 different areas.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on January 23, 2003.