Hide search tips...
- The wildcard * means "match zero or more characters" and may only be used at the end of a word.
- The wildcard ? means "match exactly one character" and cannot be used as the first character of a word.
- To search for a phrase in a document, use double-quotes to delimit your search terms -- for example, "search phrase".
- Find out more information about searching.
[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
Show search tips...