Show icon Show search tips...
Hide icon Hide search tips...

[Sy-cg-global] PROGRAM: DIMACS Workshop on Geometric Optimization

Linda Casals lindac at
Fri May 16 12:08:39 EDT 2003

DIMACS Workshop on Geometric Optimization

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

    Joe Mitchell, SUNY Stony Brook, jsbm at 
    Pankaj Agarwal, Duke University, pankaj at 

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.

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.



Monday, May 19, 2003

 8:15 -  8:55   Breakfast and Registration

 8:55 -  9:00   Opening remarks:
                Melvin Janowitz, Associate Director of DIMACS

 9:00 - 10:00   Unique Sink Orientations of Cubes and its 
                Relations to Optimization              
                Emo Welzl, ETH Zurich

10:00 - 10:30   Smoothed Analysis of Algorithms: Simplex 
		Algorithm and Numerical Analysis
                Shanghua Teng, Boston University
10:30 - 11:00   Break
11:00 - 11:30   The Protein Side-Chain Positioning Problem
                Carl Kingsford, Princeton University

11:30 - 12:00   Approximate Protein Structural Alignment in Polynomial Time
                Rachel Kolodny, Stanford University

12:00 - 12:30   Hausdorff Distance under Translation for Points and Balls
                Yusu Wang, Duke University        

12:30 -  2:00   Lunch

 2:00 -  3:00   Emerging Trends in Optimization
                Dan Bienstock, Columbia University
 3:00 -  3:30   Exact Parallel Algorithm for Computing Maximum Feasible
                Subsystems of Linear Relations
                Vera Rosta, McGill University

 3:30 -  4:00   Improved Embeddings of Metrics into Trees
                Satish Rao, UC Berkeley

 4:00 -  4:30   Break

 4:30 -  5:00   Online Searching with Turn Cost
                Erik Demaine, MIT

 5:00 -  5:30   Leave no Stones Unturned: Improved Approximation 
                Algorithms for Degree-Bounded Minimum Spanning Trees
                Raja Jothi, UT Dallas

 5:30 -  6:00   Constructing Spanners of Different Flavors
                Joachim Gudmundsson

Tuesday,  May 20, 2003

 8:30 -  9:00   Breakfast and registration

 9:00 - 10:00   Random Walks and Geometric Algorithms
                Santosh Vempala, MIT

10:00 - 10:30   Approximation Algorithms for k-Center Clustering
                Piyush Kumar, SUNY Sony Brook

10:30 - 11:00   Break

11:00 - 11:30   Computing Projective Clusters via Certificates
                Cecilia M. Procopiuc, AT&T Labs

11:30 - 12:00   Shape Fitting with Outliers
                Sariel Har-Peled, UIUC

12:00 - 12:30   Approximate Minimum Volume Enclosing Ellipsoids 
                Using Core Sets
                Alper Yildirim, SUNY Sony Brook

12:30 -  2:00   Lunch

 2:00 -  3:00   Geometric Optimization and Arrangements
                Micha Sharir, Tel Aviv University

 3:00 -  3:30   Approximating the k-Radius of High-Dimensional Point Sets
                Kasturi Varadarajan, University of Iowa

 3:30 -  4:00   Break

 4:00 -  5:00   Approximation Schemes for Geometric NP-Hard Problems: 
                A Survey
                Sanjeev Arora, Princeton University

  5:00 - 5:30   TSP with Neighborhoods of Varying Size
                Matthew Katz, Ben Gurion University

  5:30 - 6:00   Touring a Sequence of Polygons
                Alon Efrat, University of Arizona

Wednesday,  May 21, 2003
 8:30 -  9:00   Breakfast and registration

 9:00 - 10:00   Quasiconvex Programming
                David Eppstein, UC Irvine

10:00 - 10:30   Engineering Geometric Optimization Algorithms: 
                Some Experiments
                Herve Bronnimann, Polytechnic University

10:30 - 11:00   Subtraction in Geometric Searching
                Bernard Chazelle

11:00 - 11:30   Minimum Separation in Weighted Subdivisions
                Ovidiu Daescu and James Palmer

11:30 - 12:30   Lunch

12:30 -  1:00   Some Data Streaming Problems in Computational Geometry
                S. Muthukrishnan, Rutgers University

 1:00 - 1:30    Streaming Geometric Optimization Using Graphics Hardware
                Suresh Venkatasubramanian, AT&T Labs

 1:30 - 2:00    Efficient Algorithms for Shared Camera Control
                Vladlen Koltun, UC Berkeley

Registration Fees: 

(Pre-registration deadline: May 12, 2003) 

Regular rate
Preregister before deadline $120/day
After preregistration deadline $140/day

Reduced Rate*
Preregister before deadline $60/day
After preregistration deadline $70/day

Preregister before deadline $10/day
After preregistration deadline $15/day

DIMACS Postdocs $0

Non-Local Graduate & Undergraduate students
Preregister before deadline $5/day
After preregistration deadline $10/day

Local Graduate & Undergraduate students $0
(Rutgers & Princeton)

DIMACS partner institution employees** $0

DIMACS long-term visitors*** $0

Registration fee to be collected on site, cash, check, VISA/Mastercard

Our funding agencies require that we charge a registration fee for the
workshop. Registration fees cover participation in the workshop, all
workshop materials, breakfast, lunch, breaks, and any scheduled social
events (if applicable).

* College/University faculty and employees of non-profit organizations
will automatically receive the reduced rate. Other participants may
apply for a reduction of fees. They should email their request for the
reduced fee to the Workshop Coordinator at
workshop at  Include your name, the Institution you
work for, your job title and a brief explanation of your
situation. All requests for reduced rates must be received before the
preregistration deadline. You will promptly be notified as to the
decision about it.

** Fees for employees of DIMACS partner institutions are waived.
DIMACS partner institutions are: Rutgers University, Princeton
University, AT&T Labs - Research, Bell Labs, NEC Laboratories America
and Telcordia Technologies. Fees for employees of DIMACS affiliate
members Avaya Labs, IBM Research and Microsoft Research are also

***DIMACS long-term visitors who are in residence at DIMACS for two or
more weeks inclusive of dates of workshop.


Information on participation, registration, accommodations, and travel
can be found at:


More information about the Dimacs-sy-cg-global mailing list