Program for the ACM- SIAM, Symposium on Discrete Algorithms

Saturday, January 11, 2003
7:30 AM - 6:30 PM Registration
Pre-Function Area
6:00 PM - 8:00 PM Welcome Reception
Maryland Suite
Sunday January 12, 2003
7:30 AM - 4:30 PM Registration
Pre-Function Area
8:30 AM - 9:20 AM Continental Breakfast
Constellation A
9:30 AM - 11:10 AM

Session 1A

9:30 AM - Optimal Parallel Selection
Yijie Han, University of Missouri, Kansas City

9:55 AM - Selection with Monotone Comparison Costs
Sampath Kannan, Sanjeev Khanna, University of Pennsylvania

10:20 AM - Property Testing of Data Dimensionality
Robert Krauthgamer, University of California; Ori Sasson, The Hebrew University

10:45 AM - Comparing Top K Lists
Ronald Fagin, Ravi Kumar, D. Sivakumar, IBM Almaden Research Center

Constellation C

Session 1B

9:30 AM - Algorithms for Power Savings
Sandy Irani, University of California, Irvine; Sandeep Shukla, Virginia Tech; Rajesh Gupta, University of California, San Diego

9:55 AM - Dynamic TCP Acknowledgement: Penalizing Long Delays
Susanne Albers, Freiburg University; Helge Bals, Dortmund University

10:20 AM - Approximately Optimal Control of Fluid Networks
Lisa Fleischer, Carnegie Mellon University; Jay Sethuraman, Columbia University

10:45 AM - Minimum Cost Flows Over Time without Intermediate Storage
Lisa Fleischer, Carnegie Mellon University; Martin Skutella, Technical University Berlin

Constellation D
Session 1C

9:30 AM - Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle
Michael Elkin, Weizmann Institute of Science; Guy Kortsarz, Rutgers University

9:55 AM - On the Performance of User Equilibria in Traffic Networks
Andreas Schulz, Nicolas Stier Moses; Massachusetts Institute of Technology

10:20 AM - Faster Approximation Algorithms for the Minimum Latency Problem
Aaron Archer, Cornell University; David Williamson, IBM Almaden Research Center

10:45 AM - Data Migration to Minimize the Average Completion Time
Yoo-Ah Kim, University of Maryland

Constellation E
11:10 AM - 11:30 AM Coffee Break
Constellation A
11:30 AM - 12:30 PM

Session 2 - IP#1

Browsing Around a Digital Library
Ian H. Witten, University of Waikato, New Zealand

Constellation B
12:30 PM - 2:00 PM Luncheon
Constellation A
2:00 PM - 3:40 PM

Session 3A

2:00 PM - Binary Space Partitions for 3D Subdivisions
John Hershberger, Mentor Graphics Corporation; Subhash Suri, University of California, Santa Barbara

2:25 PM - Allocating Vertex pi-guards in Simple Polygons via Pseudo-Triangulations
Bettina Speckmann, Csaba D. Tóth, Institut für Theoretische Informatik Zurich

2:50 PM - Straight-Skeleton Based Contour Interpolation
Gill Barequet, Aya Levi-Steiner, Dvir Steiner, Technion; Michael T. Goodrich, University of California, Irvine

3:15 PM - Mobius-Invariant Natural Neighbor Interpolation
Marshall Bern, Palo Alto Research Center; David Eppstein, University of California, Irvine

Constellation C
Session 3B

2:00 PM - Improved Bounds on the Average Length of Longest Common Subsequences
Lueker George, University of California, Irvine

2:25 PM - Directed Scale-Free Graphs
Bela Bollobas, Christian Borgs, Jennifer Chayes, Microsoft Research; Oliver Riordan, Trinity College, Cambridge

2:50 PM - The Cover Time of Sparse Random Graphs
Alan Frieze, Carnegie Mellon University; Colin Cooper, London University

3:15 PM - Perfect Matchings in Random Graphs with Prescribed Minimal Degree
Alan Frieze, Carnegie Mellon University; Boris Pittel, Ohio State University

Constellation D
Session 3C

2:00 PM - Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
Dieter Kratsch, University of Metz, Ross M. McConnell, Colorado State University; Kurt Mehlhorn, Max Planck Instit fuer Informatik; Jerry Spinrad, Vanderbilt University

2:25 PM - Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up
Fedor Fomin, Paterborn University, Germany; Dimitrios Thilikos, Universitat Politècnica de Catalunya

2:50 PM - Quick and Good Facility Location
Mikkel Thorup, AT&T Labs-Research

3:15 PM - Chain Decompositions and Independent Trees in 4-Connected Graphs
Xingxing Yu, Sean Curran, Orlando Lee, Georgia Institute of Technology

Constellation E
3:40 PM - 4:05 PM
Coffee Break
Constellation A
4:05 PM - 5:45 PM
Session 4A - Constellation C

4:05 PM - Optimizing Misdirection
Piotr Berman, Pennsylvania State University; Piotr Krysta, Max-Planck Institute

4:30 PM - Online Learning in Online Auctions
Avrim Blum, Carnegie Mellon University; Vijay Kumar,; Atri Rudra, IBM India and University of Texas at Austin; Felix Wu, University of California at Berkeley

4:55 PM - An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
Aaron Archer, Eva Tardos, Cornell University; Christos Papadimitriou, Kunal Talwar, University of California, Berkeley

5:20 PM - Competitiveness via Consensus
Andrew Goldberg, Microsoft Research; Jason Hartline, University of Washington

Constellation C
Session 4B

4:05 PM - Pass Efficient Algorithms for Approximating Large Matrices
Petros Drineas, Ravi Kannan, Yale University

4:30 PM - Rangesum Histograms
Muthukrishnan S, AT&T Research and Rutgers University; Martin Strauss, AT&T Labs

4:55 PM - Approximation of Functions Over Redundant Dictionaries Using Coherence
Anna Gilbert, Martin Strauss AT&T Labs-Research; S. Muthukrishnan, Rutgers University and AT&T Research

5:20 PM - Counting Inversions in Lists
Anupam Gupta, Francis Zane, Lucent Bell Labs

Constellation D
Session 4C

4:05 PM - Certifying and Repairing Solutions to Large LPs -- How Good are LP-Solvers?
Stefan Funke, Marcel Dhiflaoui, Carsten Kwappik, Kurt Mehlhorn, Michael Seel, Elmar Schoemer, Ralph Schulte, Dennis Weber, Max-Planck-Institut fur Informatik

4:30 PM - An Improved Approximation Algorithm for the 0-Extension Problem
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar, University of California, Berkeley

4:55 PM - Packing Steiner Trees
Kamal Jain, Microsoft, Mohammad Mahdian, Massachusetts Institute of Technology; Mohammad R. Salavatipour, University of Toronto

5:20 PM - Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
Eran Halperin, University of California, Berkeley; Guy Kortsarz, Rutgers University; Robert Krauthgamer, University of California; Aravind Srinivasan, Nan Wang, University of Maryland

Constellation E
Monday January 13, 2003
7:30 AM - 4:30 PM Registration
Pre-Function Area
8:00 AM - 8:50 AM Continental Breakfast
Constellation A
9:00 AM - 11:05 AM
Session 5A

9:00 AM - The Flow Complex: A Data Structure for Geometric Modeling
Joachim Giesen, John Matthias, ETH Zurich

9:25 AM - Graded Conforming Delaunay Tetrahedralization with Bounded Radius-Edge Ratio
Siu-Wing Cheng, Sheung-Hung Poon, Hong Kong University of Science and Technology

9:50 AM - On the Combinatorial Complexity of Euclidean Voronoi Cells and Convex Hulls of d-Dimensional Spheres
Jean-Daniel Boissonnat, Menelaos Karavelas INRIA Sophia-Antipolis

10:15 AM - Perturbations and Vertex Removal in a 3D Delaunay Triangulation
Olivier Devillers, Monique Teillaud, INRIA, France

10:40 AM - Root Comparison Techniques Applied to Computing the Additively Weighted Voronoi diagram
Menelaos Karavelas, Ioannis Z. Emiris, INRIA Sophia-Antipolis

Constellation C
Session 5B

9:00 AM - Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources
Mary Cryan, Martin Dyer, Haiko Muller, University of Leeds; Leen Stougie, Eindhoven University of Technology

9:25 AM - Smaller Explicit Superconcentrators
Noga Alon, Tel Aviv University; Michael Capalbo, Institute for Advanced Study

9:50 AM - A (1+\epsilon)Ε-Approximation Algorithm for Partitioning Hypergraphs Using a New AlgorithmicVersion of the Lovász Local Lemma
Mohammad R. Salavatipour, University of Toronto

10:15 AM - A Spectral Technique for Random Satisfiable 3CNF Formulas
Abraham Flaxman, Carnegie Mellon University

10:40 AM - Random MAX 2-SAT and MAX CUT
Don Coppersmith, David Gamarnik, Gregory Sorkin, IBM Research; Mohammad Taghi Hajiaghayi, Massachusetts Institute of Technology

Constellation D
Session 5C

9:00 AM - Space-Efficient Finger Search on Degree-Balanced Search Trees
Guy Blelloch, Bruce M. Maggs, Shan Leung Maverick Woo, Carnegie Mellon

9:25 AM - Skip Graphs
James Aspnes, Gauri Shah, Yale University

9:50 AM - Maintaining All-Pairs Approximate Shortest Paths under Deletion of Edges
Surender Baswana, Sandeep Sen, Indian Institute of Technology Delhi, India; Ramesh Hariharan, Indian Institute of Science Bangalore, India

10:15 AM - A Faster and Simpler Fully Dynamic Transitive Closure
Liam Roditty, Tel-Aviv University

Constellation E
11:05 AM - 11:30 AM Coffee Break
Constellation A
11:30 AM - 12:30 PM

Session 6 - IP#2

Data Streams: Algorithms and Applications
S. Muthukrishnan, Rutgers University and AT&T Shannon Labs

Constellation B
12:30 PM - 2:00 PM Lunch (Attendees on their own)
2:00 PM - 3:40 PM
Session 7A

2:00 PM - Sparse Distance Preservers and Additive Spanners
Béla Bollobás, Microsoft Research; Don Coppersmith, IBM Research; Michael Elkin, Weizmann Institute of Science

2:25 PM - Multi-Embedding and Path Approximation of Metric Spaces
Yair Bartal, Manor Mendel, The Hebrew University

2:50 PM - Approximation Algorithm for Embedding Metrics into a Two-Dimensional Space
Mihai Badoiu, Massachusetts Institute of Technology

3:15 PM - On the Complexity of Distance-based Evolutionary Tree Reconstruction
Valerie King, Hewlett Packard Labs and University of Victoria, Li Zhang, and Yunhong Zhou, Hewlett Packard Labs

Constellation C
Session 7B

2:00 PM - Improved Results for Directed Multicut
Anupam Gupta, Lucent Bell Labs

2:25 PM - Algorithms for k-Colouring and Finding Maximal Independent Sets
Jesper Makholm Byskov, University of Aarhus

2:50 PM - Equitable Colorings with Constant Number of Colors
Sriram Pemmaraju, Kittikorn Nakprasit, University of Iowa; Alexandr Kostochka, University of Illinois

3:15 PM - Better Performance Bounds for Finding the Smallest $k$-Edge Connected Spanning Subgraph of a Multigraph
Harold Gabow, University of Colorado, Boulder

Constellation D
Session 7C

2:00 PM - A Note on the Set Systems used for Broadcast Encryption
Alexander Russell, University of Connecticut; Ravi Kumar, IBM Almaden

2:25 PM - Lower Bounds for Collusion-Secure Fingerprinting
Chris Peikert, Abhi Shelat, Adam Smith, Massachusetts Institute of Technology

2:50 PM - Quantum Property Testing
Harry Buhrman, Hein Rohrig, Centrum voor Wiskunde en Informatica; Lance Fortnow, NEC Research Institute; Ilan Newman, University of Haifa

3:15 PM - Quantum Algorithms for Some Hidden Shift Problems
Sean Hallgren, Caltech; Wim van Dam, Lawrence Ip, University of California, Berkeley

Constellation E
3:40 PM - 4:05 PM Coffee Break
Constellation A
4:05 PM - 5:45 PM
Session 8A

4:05 PM - Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk
Ashish Goel, University of Southern California; Deborah Estrin, University of California, Los Angeles

4:30 PM - Non-independent Randomized Rounding
Benjamin Doerr, University of Kiel

4:55 PM - Minimizing Weighted Flow Time
Nikhil Bansal, Kedar Dhamdhere, Carnegie Mellon University

5:20 PM - A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-Perfect Graph
Friedrich Eisenbrand, Stefan Funke, Max-Planck-Institut für Informatik; Naveen Garg, Indian Institute of Technology Delhi; Jochen Koenemann, Carnegie Mellon University

Constellation C
Session 8B

4:05 PM - Lower Bounds for Embedding of Edit Distance into Normed Spaces
Alexandr Andoni, Piotr Indyk, Sofya Raskhodnikova, Massachusetts Institute of Technology; Michel Deza, École normale supérieure, France; Anupam Gupta, Lucent Bell Labs

4:30 PM - Embedding k-Outerplanar Graphs into ell_1
Chandra Chekuri, Anupam Gupta, Lucent Bell Labs; Ilan Newman, Yuri Rabinovich, University of Haifa; Alistair Sinclair, University of California, Berkeley

4:55 PM - Embeddings and Non-approximability of Geometric Problems
Venkatesan Guruswami, University of California, Berkeley; Piotr Indyk, Massachusetts Institute of Technology

5:20 PM - Better Algorithms for High-dimensional Proximity Problems via Asymmetric Embeddings
Piotr Indyk, Massachusetts Institute of Technology

Constellation D
Session 8C

4:05 PM - Lower Bounds for External Memory Dictionaries
Gerth Stølting Brodal, Rolf Fagerberg, BRICS, Aarhus University

4:30 PM - Online Paging with Limited Associativity
Enoch Peserico, Massachusetts Institute of Technology

4:55 PM - The Set-Associative Cache Performance of Search Trees
James Fix, Reed College

5:20 PM - Computing Strongly Connected Components in a Linear Number of Symbolic Steps
Raffaella Gentilini, Alberto Policriti, University of Udine; Carla Piazza, University of Venezia

Constellation E
6:00 PM - 7:00 PM SIAM Business Meeting
Constellation A
Tuesday January 14, 2003
7:30 AM - 4:00 PM Registration
Pre-Function Area
  8:30 AM - 9:20 AM Continental Breakfast
Constellation A
9:00 AM - 11:05 AM

Session 9A

9:00 AM - On the Rectilinear Crossing Number of Complete Graphs
Uli Wagner, ETH Zurich

9:25 AM - Matching Planar Maps
Helmut Alt, Günter Rote, Freie Universitaet Berlin; Alon Efrat, Carola Wenk, University of Arizona

9:50 AM - Dynamic Generators of Topologically Embedded Graphs
David Eppstein, University of California, Irvine

10:15 AM - Computing Homotopic Shortest Paths in the Plane
Sergei Bespamyatnikh, Duke University

10:40 AM - Fully-Dynamic Two Dimensional Orthogonal Range and Line Segment Intersection Reporting in Logarithmic Time
Christian Worm Mortensen, IT University of Copenhagen

Constellation C
Session 9B

9:00 AM - Edge Disjoint Paths Revisited
Chandra Chekuri, Lucent Bell Labs; Sanjeev Khanna, University of Pennsylvania

9:25 AM - A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality
Markus Blaeser, Universitaet zu Luebeck

9:50 AM - Approximating Asymmetric Maximum TSP
Moshe Lewenstein, Maxim Sviridenko, IBM Research

10:15 AM - The k-Traveling Repairman Problem
Chris Harrelson, Jittat Fakcharoenphol, Satish Rao,University of California, Berkeley

10:40 AM - Directed Graphs Requiring Large Numbers of Shortcuts
William Hesse, University of Massachusetts, Amherst

Constellation D
Session 9C

9:00 AM - Implicit Dictionaries Supporting Searches and Amortized Updates in O(\log n \log\log n) Time
Gianni Franceschini, Roberto Grossi, Universita' di Pisa

9:25 AM - Compact Representations of Separable Graphs
Dan Blandford, Guy Blelloch, Ian Kash, Carnegie Mellon University

9:50 AM - Labeling Schemes for Small Distances in Trees
Stephen Alstrup, Philip Bille, Theis Rauhe, IT University of Copenhagen

10:15 AM - On AC0 Implementations of Fusion Trees and Atomic Heaps
Mikkel Thorup, AT&T Labs-Research

Constellation E
11:05 AM - 11:30 AM Coffee Break
Constellation A
11:30 AM - 12:30 PM

Session 10 - IP#3

Who Cares About Permanents?
Persi Diaconis, Stanford University

Constellation B
12:30 PM - 2:00 PM Lunch (Attendees on their own)
2:00 PM - 3:40 PM

Session 11A

2:00 PM - Between O(nm) and O(n^\alpha)
Dieter Kratsch, Universite de Metz, Jerry Spinrad, EECS Department

2:25 PM - Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons
Devdatt Dubhashi, Chalmers University of Technology, Sweden; Alessandro Mei, Alessandro Panconesi, Università di Roma "La Sapienza", Italy; Jaikumar Radhakrishnan, Tata Institute of Fundamental Research, India; Aravind Srinivasan, University of Maryland

2:50 PM - A 5/4-Approximation Algorithm for Minimum 2-Edge-Connectivity
Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan, University of Texas, Dallas

3:15 PM - Fault-Tolerant Facility Location
Chaitanya Swamy, David Shmoys, Cornell University

Constellation C
Session 11B

2:00 PM - Efficient Sequences of Trials
Edith Cohen, AT&T Labs; Amos Fiat, Haim Kaplan, Tel Aviv University

2:25 PM - Pursuit-Evasion with Imprecise Target Location
Günter Rote, Freie Universität Berlin

2:50 PM - Unconditional Proof of Tightness of Johnson Bound
Venkatesan Guruswami, University of California, Berkeley; Igor Shparlinski, Macquarie University, Australia

3:15 PM - Deterministic Identity Testing for Multivariate Polynomials
Richard Lipton, Nisheeth Vishnoi, Georgia Tech

Constellation D
Session 11C

2:00 PM - Competitive Queueing Policies for QoS Switches
Nir Andelman, Yishay Mansour, Tel-Aviv University; An Zhu, Stanford University

2:25 PM - Dynamic Routing on Networks with Fixed-Size Buffers
William Aiello, AT&T Labs-Research, Eyal Kushilevitz, Adi Rosen, Technion; Rafail Ostrovsky, Telcordia Technologies

2:50 PM - Dynamic Construction of Bluetooth Scatternets of Fixed Degree and Low Diameter
Lali Barriere, Universitat Politecnica de Catalunya; Pierre Fraigniaud, Centre National de la Recherche Scientifique; Lata Narayanan, Jaroslav Opatrny, Concordia University

3:15 PM - Scheduling Techniques for Media-on-Demand
Amotz Bar-Noy, Brooklyn College, Richard Ladner, University of Washington; Tami Tamir, Technion

Constellation E
3:40 PM - 4:05 PM Coffee Break
Constellation A
4:05 PM - 5:45 PM
Session 12A

4:05 PM - Smaller Core-Sets for Balls
Mihai Badoiu, Massachusetts Institute of Technology; Kenneth L Clarkson, Bell Labs

4:30 PM - Zonotopes as Bounding Volumes
An Nguyen, Leonidas Guibas, Stanford University; Li Zhang, Hewlett Packard Labs

4:55 PM - Sublinear Approximation of Euclidean Minimum Spanning Tree
Artur Czumaj, NJ Institute of Technology; Funda Ergun, Lance Fortnow, Avner Magen, Ronitt Rubinfeld, NEC Research; Ilan Newman, University of Haifa; Christian Sohler, University of Paderborn

5:20 PM - An Approximation Algorithm for Cutting Out Convex Polygons
Adrian Dumitrescu, University of Wisconsin-Milwaukee

Constellation C
Session 12B

4:05 PM - Inferring Tree Topologies Using Flow Tests
S. Muthukrishnan, Rutgers University; Torsten Suel, Polytechnic University; Radek Vingralek, Intertrust Tech

4:30 PM - Wavelength Assignment and Generalized Interval Graph Coloring
Peter Winkler, Lisa Zhang, Bell Labs

4:55 PM - An Improved Approximation Algorithm for the Partial Latin Square Extension Problem
Carla Gomes, Rommel Regis, David Shmoys, Cornell University

5:20 PM - Multirate Rearrangeable Clos Networks and a Generalized Bipartite Graph Edge Coloring Problem
Hung Ngo, State University of New York at Buffalo; Van Vu, University of California, San Diego

Constellation D
Session 12C

4:05 PM - High-Order Entropy-Compressed Text Indexes
Roberto Grossi, University of Pisa, Ankur Gupta, Jeffrey Scott Vitter, Duke University

4:30 PM - Multidimensional Matching and Fast Search in Suffix Trees
Richard Cole, New York University; Moshe Lewenstein, IBM Research

4:55 PM - Inplace 2D Matching in Compressed Images
Amihood Amir, AT&T Labs - Research; Gad Landau, Haifa University and Polytechnic University; Dina Sokol, Bar-Ilan University

5:20 PM - The Similarity Metric
Ming Li, University of California, Santa Barbara/University of Waterloo; Xin Chen, University of California, Santa Barbara; Xin Li, Bin Ma, University of Western Ontario; Paul Vitanyi, Centrum voor Wiskunde en Informatica

Constellation E