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

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

Sarah Donnelly sarahd at dimacs.rutgers.edu
Fri May 2 15:21:08 EDT 2003



DIMACS Workshop on Geometric Optimization

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

Organizers: 
    Joe Mitchell, SUNY Stony Brook, jsbm at ams.sunysb.edu 
    Pankaj Agarwal, Duke University, pankaj at cs.duke.edu 

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.

****************************************************************

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

Postdocs
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
accepted.

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 dimacs.rutgers.edu.  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
waived.

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

*********************************************************

                   PROGRAM


Monday, May 19, 2003

 8:15-8:55     Breakfast and Registration

 8:55-9:00     Opening remarks:
               Fred S. Roberts, 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 Proble
               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-02:00   Lunch


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

 03:30-04:00   Improved Embeddings of Metrics into Trees
               Satish Rao, UC Berkeley


 04:00-04:30   Break


 04:30-05:00   Online Searching with Turn Cost
               Erik Demaine, MIT

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

 05:30-06:00   Constructing Spanners of Different Flavors
               Joachim Gudmundsson



Tuesday,  May 20, 2003


 08:15-09:00   Breakfast and registration

 09: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-02:00   Lunch


 02:00-03:00   Geometric Optimization and Arrangements
               Micha Sharir, Tel Aviv University

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


 03:30-04:00   Break


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

 05:00-05:30   TSP with Neighborhoods of Varying Size
               Matya Katz, Ben Gurion University

 05:30-06:00   Touring a Sequence of Polygons
               Alon Efrat, University of Arizona


Wednesday,  May 21, 2003


 09: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-01:00   Some Data Streaming Problems in Computational Geometry
               S. Muthukrishnan, Rutgers University

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

 01:30-02:00   Efficient Algorithms for Shared Camera Control
               Vladlen Koltun, UC Berkeley





*********************************************************

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


    http://dimacs.rutgers.edu/Workshops/GeomOpt/

  
  **PLEASE BE SURE TO PRE-REGISTER EARLY**

*********************************************************






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