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

Workshop Program:

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 Stony 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 Stony 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
               

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage