ACM-SIAM Symposium on Discrete Algorithms - Final Program

The paper title and/or authors listed on the web program appear as
originally received. All paper titles and authors will be listed
*correctly* in the final printed program distributed on-site.

Saturday | Sunday | Monday | Tuesday

Date
Day
Event and Time
Session ID
Time
Title
Authors
10-Jan-04
 
Saturday
 
Registration Open
8:00 AM - 6:30 PM
 
 
  
 
 
  
ACM - SIAM SODA Welcome Reception
6:00 PM - 8:00 PM
11-Jan-04
 
Sunday
 
Registration Open
8:00 AM - 5:00 PM
 
 
  
 
 
  
Continental Breakfast 8:30 AM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Concurrent Sessions
9:00 AM - 11:05 AM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1A
 
 
 
 
9:00 AM
Succinct Tree Representations for XML Documents Richard F. Geary, Rajeev Raman and Venkatesh Raman
9:25 AM
Compact Representations of Ordered Sets Daniel Blandford and Guy E. Blelloch
9:50 AM
Tight Bounds for the Partial-Sums Problem Mihai Patrascu and Erik D. Demaine
10:15 AM
Saving David Nelson with Bloomier Filters Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld and Ayellet Tal
10:40 AM
Meldable RAM Priority Queues and Minimum Directed Spanning Trees Ran Mendelson, Mikkel Thorup and Uri Zwick
1B
 
 
 
 
9:00 AM
Finding a Long Directed Cycle Harold N. Gabow and Shuxin Nie
9:25 AM
A New Algorithm for Normal Dominance Constraints Manuel Bodirsky, Denys Duchier and Sebastian Miehle
9:50 AM
Rank-Maximal Matchings Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail and Katarzyna Paluch
10:15 AM
Network Failure Detection and Graph Connectivity Jon Kleinberg, Mark Sandler and Alexandrs Slivkins
10:40 AM
The Directed Circular Arrangement Problem Joseph (Seffi) Naor and Roy Schwartz
1C
 
 
 
 
9:00 AM
Variable Length Path Coupling Thomas P. Hayes and Eric Vigoda
9:25 AM
Linear Phase Transition in Random Linear Constraint Satisfaction David Gamarnik
9:50 AM
Quantitative Stochastic Parity Games Krishnendu Chatterjee, Marcin Jurdzinski and Thomas A. Henzinger
10:15 AM
On Distributions Computable by Random Walks on Graphs Guy Kindler and Dan Romik
10:40 AM
Exponential Bounds for DPLL Below the Satisfiability Threshold Dimitris Achlioptas, Paul Beame and Michael Molloy
Coffee Break
11:05 AM - 11:30 AM
 
 
  
Invited Plenary Session
11:30 AM - 12:30 PM
2
11:30 AM
Who Says You Have to Look at the Input? The Brave New World of Sublinear Computing? Bernard Chazelle, Princeton University and NEC Laboratories America, Inc.
Luncheon
12:30 PM - 2:00 PM
 
 
  
Concurrent Sessions
2:00 PM - 4:05 PM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3A
 
 
 
 
2:00 PM
Complexity Classification of Network Information Flow Problems April Rasala Lehman and Eric Lehman
2:25 PM
An Improved Data Stream Algorithm for Frequency Moments Don Coppersmith and Ravi Kumar
2:50 PM
Efficient Estimation Algorithms for Neighborhood Variance and Other Moments Edith Cohen and Haim Kaplan
3:15 PM
Optimal Space Lower Bounds for all Frequency Moments David Woodruff
3:40 PM
Analysis of Routing Protocols for Chord Prasanna Ganesan and Gurmeet Singh Manku
3B
 
 
 
 
2:00 PM
Approximation Schemes for Multidimensional Packing Jose R. Correa and Claire Kenyon
2:25 PM
New Approximability and Inapproximability Results for 2-dimensional Bin Packing Nikhil Bansal and Maxim Sviridenko
2:50 PM
On Rectangle Packing: Maximizing Benefits Klaus Jansen and Guochuan Zhang
3:15 PM
Optimal Online Bounded Space Multidimensional Packing Leah Epstein and Rob van Stee
3:40 PM
Windows Scheduling as a Restricted Version of Bin Packing Amotz Bar-Noy, Richard E. Ladner and Tami Tamir
3C
 
 
 
 
2:00 PM
Special Edges, and Approximating the Smallest Directed k-edge Connected Spanning Subgraph Harold N. Gabow
2:25 PM
On Colorings of Squares of Outerplanar Graphs Geir Agnarsson and Magnus M. Halldorsson
2:50 PM

Detecting Short Directed Cycles using Rectangular Matrix Multiplication and Dynamic Programming

Raphael Yuster and Uri Zwick

3:15 PM
Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs Yuval Emek and David Peleg
3:40 PM
Approximate Distance Oracles for Unweighted Graphs in (n2) Time Surender Baswana and Sandeep Sen
Coffee Break
4:05 PM - 4:30 PM
 
 
  
Concurrent Sessions
4:30 PM - 6:35 PM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4A
 
 
 
 
4:30 PM
Retroactive Data Structures Erik D. Demaine, John Iacono and Stefan Langerman
4:55PM
Proximity Mergesort: Optimal In-Place Sorting in the Cache-Oblivious Model Gianni Franceschini
5:20 PM
The Number of Bit Comparisons Used by Quicksort: An Average-case Analysis James Allen Fill and Svante Janson
5:45 PM
Family Trees: An Ordered Dictionary with Optimal Congestion Kevin Zatloukal and Nicholas J. A. Harvey
6:10 PM
Deterministic Concurrent Searchable Data Structures: Upper and Lower Bounds Baruch Awerbuch and Christian Scheideler
4B
 
 
 
 
4:30 PM
Improved Upper Bounds for 3-SAT Kazuo Iwama and Suguru Tamaki
4:55PM
Locally Satisfiable Formulas Daniel Kral
5:20 PM
On Braess's Paradox Henry Lin, Tim Roughgarden and Eva Tardos
5:45 PM
Multicommodity Facility Location R. Ravi and A. Sinha
6:10 PM
SRPT Optimally Uses Faster Machines to Minimize Flow Time Jason McCullough and Eric Torng
4C
 
 
 
 
4:30 PM
A Faster Distributed Protocol for Constructing the Minimum Spanning Tree Michael Elkin
4:55PM
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms Camil Demetrescu, Stefano Emiliozzi and Giuseppe F. Italiano
5:20 PM
Graph Decomposition and a Greedy Algorithm for Edge-Disjoint Paths Kasturi Varadarajan and Ganesh Venkataraman
5:45 PM
Models of Greedy Algorithms for Graph Problems Sashka Davis and Russell Impagliazzo
6:10 PM
The List Partition Problem for Graphs Kathie Cameron, Elaine E. Eschen and Chinh T. Hoang and R. Sritharan
12-Jan-04
 
Monday
 
Registration Open
8:00 AM - 5:00 PM
 
 
  
Continental Breakfast 8:30 AM
 
 
  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Concurrent Sessions
9:00 AM - 11:05 AM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5A
 
 
 
 
9:00 AM
A Time Efficient Delaunay Refinement Algorithm Gary L. Miller
9:25 AM
Almost-Delaunay Simplices: Nearest Neighbor Relations for Imprecise Points Deepak Bandyopadhyay and Jack Snoeyink
9:50 AM
Output-Sensitive Construction of the Union of Triangles Eti Ezra and Micha Sharir
10:15 AM
An Optimal Randomized Algorithm for Maximum Tukey Depth Timothy M. Chan
10:40 AM
Minimizing the Stabbing Number of Matchings, Trees, and Triangulations Sandor P. Fekete, Marco Luebbecke and Henk Meijer
5B
 
 
 
 
9:00 AM
Adaptive Sampling for Quickselect Conrado Martinez, Daniel Panario and Alfredo Viola
9:25 AM
Fast Mixing for Independent Sets, Colorings and Other Models on Trees Fabio Martinelli, Alistair Sinclair and Dror Weitz
9:50 AM
Slow Mixing of the Glauber Dynamics for the Hard-core Model on David Galvin and Prasad Tetali
10:15 AM
Probabilistic Analysis of Knapsack Core Algorithms Rene Beier and Berthold Voecking
10:40 AM
Torpid Mixing of Simulated Tempering on the Potts Model Nayantara Bhatnagar and Dana Randall
5C
 
 
 
 
9:00 AM
Minimum Moment Steiner Trees Wangqi Qiu and Weiping Shi
9:25 AM
Approximation Schemes for Minimum 2-Edge-Connected and Biconnected Subgraphs in Planar Graphs Artur Czumaj, Michelangelo Grigni, Papa Sissokho and Hairong Zhao
9:50 AM
Approximation Schemes for Metric Bisection and Partitioning W. Fernandez de la Vega, Marek Karpinski and Claire Kenyon
10:15 AM
Computing Maximally Separated Sets in the Plane and Independent Sets in the Intersection Graph of Unit Disks Pankaj K. Agarwal, Mark Overmars and Micha Sharir
10:40 AM
Correlation Clustering: Maximizing Agreements via Semidefinite Programming Chaitanya Swamy
Coffee Break
11:05 AM - 11:30 AM
 
 
  
Invited Plenary Session
11:30 AM - 12:30 PM
6
11:30 AM
Quantum Computing Raymond Laflamme, Institute for Quantum Computing, University of Waterloo, Canada, and Perimeter Institute for Theoretical Physics, Waterloo, Canada
Lunch Break
12:30 PM - 2:00 PM
 
 
  
Concurrent Sessions
2:00 PM - 4:05 PM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7A
 
 
 
 
2:00 PM
Interpolation Search for Non-Independent Data Erik D. Demaine, Thouis Jones and Mihai Patrascu
2:25 PM
Dynamizing Static Algorithms with Applications to Dynamic Trees and History Independence Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes and Shan Leung Maverick Woo
2:50 PM
Caching Queues in Memory Buffers Dilys Thomas and Rajeev Motwani
3:15 PM
LAND: Locality Aware Networks for Distributed Hash Tables Ittai Abraham, Dahlia Malkhi and Oren Dobzinski
3:40 PM
A Note on the Nearest Neighbor in Growth-Restricted Metrics Kirsten Hildrum and John Kubiatowicz and Satish Rao
7B
 
 
 
 
2:00 PM
Buffer Minimization Using Max-Coloring Sriram V. Pemmaraju, Rajiv Raman and Kasturi Varadarajan
2:25 PM
On Minimizing the Total Flow Time on Multiple Machines Nikhil Bansal
2:50 PM
Matrix Rounding and Approximation Benjamin Doerr
3:15 PM
A General Approach to Online Network Optimization Problems Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder and Joseph (Seffi) Naor
3:40 PM
Approximate Local Search in Combinatorial Optimization James B. Orlin, Abraham P. Punnen and Andreas S. Schulz
7C
 
 
 
 
2:00 PM
Trade-offs on the Location of the Core Node in a Network Jean-Francois Macq and Michel X. Goemans
2:25 PM
On the Convergence Time of a Path-Vector Protocol Tim Griffin and Howard Karloff
2:50 PM
Tabulation Based 4-universal Hashing with Applications to Second Moment Estimation Mikkel Thorup and Yin Zhang
3:15 PM
Approximate Budget Balanced Mechanisms with Low Communication Costs for the Multicast Cost-Sharing Problem Markus Blaeser
3:40 PM
Competitive Analysis of Organization Networks Or Multicast Acknolwedgement: How Much to Wait? Carlos Fisch Brito, Elias Koutsoupias, Shailesh Vaya
Coffee Break
4:05 PM - 4:30 PM
 
 
  
Concurrent Sessions
4:30 PM - 6:35 PM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8A
 
 
 
 
4:30 PM
Indexing Equals Compression: Experiments on Suffix Arrays and Trees Roberto Grossi, Ankur Gupta and Jeffrey Scott Vitter
4:55PM
Approximate Nearest Neighbor under Edit Distance via Product Piotr Indyk
5:20 PM
Fast Approximate Pattern Matching with Few Indels via Embeddings Mihai Badoiu and Piotr Indyk
5:45 PM
Lyndon Words with a Fixed Standard Right Factor Frederique Bassino, Julien Clement and Cyril Nicaud
6:10 PM
Optimal Compression Boosting in Optimal Linear Time using the Burrows-Wheeler Transform Paolo Ferragina and Giovanni Manzini
8B
 
 
 
 
4:30 PM
Dimension Reduction for Ultrametrics Yair Bartal and Manor Mendel
4:55PM
Randomized k-Server Algorithms for Growth-Rate Bounded Graphs Yair Bartal and Manor Mendel
5:20 PM
The Pure Literal Rule Threshold and Cores in Random Hypergraphs Michael Molloy
5:45 PM
Efficient Algorithms for Bichromatic Separability Pankaj K. Agarwal, Boris Aronov and Vladlen Koltun
6:10 PM
The Ant and the Grasshopper: Approximation Algorithms for Stochastic Combinatorial Optimization Problems Nicole Immorlica, David Karger, Maria Minkoff, and Vahab Mirrokni
8C
 
 
 
 
4:30 PM
Frugality in Path Auctions Edith Elkind, Amit Sahai and Ken Steiglitz
4:55PM
An Exact Subexponential-Time Lattice Algorithm for Asian Options T. S. Dai and Y. D. Lyuu
5:20 PM
Structural and Algorithmic Aspects of Massive Social Networks Stephen Eubank, V.S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan and Nan Wang
5:45 PM
A Determinant-based Algorithm for Counting Matchings in a General Graph Steve Chien
6:10 PM
On the Number of Rectangular Partitions Eyal Ackerman, Gill Barequet and Ron Y. Pinter
SIAM Business Meeting
7:00 PM - 8:00 PM
 
 
  
13-Jan-04
 
Tuesday
 
Registration Open
8:00 AM - 5:00 PM
 
 
  
Continental Breakfast 8:30 AM
 
 
  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Concurrent Sessions
9:00 AM - 11:05 AM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9A
 
 
 
 
9:00 AM
Computing Equilibria for Congestion Games with (Im)perfect Information Rene Beier, Artur Czumaj, Piotr Krysta and Berthold Voecking
9:25 AM
Efficiently Decodable Codes Meeting Gilbert-Varshamov Bound for Low Rates Venkatesan Guruswami and Piotr Indyk
9:50 AM
Algorithms for Infinite Huffman-Codes Mordecai J. Golin and Kin Keung Ma
10:15 AM
A Certifying Algorithm for the Consecutive-ones Property Ross M. McConnell
10:40 AM
Generic Quantum Fourier Transforms Cristopher Moore, Daniel Rockmore and Alexander Russell
9B
 
 
 
 
9:00 AM
Quasiconvex Analysis of Backtracking Algorithms David Eppstein
9:25 AM
Navigating Nets: Simple Algorithms for Proximity Search Robert Krauthgamer and James R. Lee
9:50 AM
Approximating the Two-Level Facility Location Problem via a Quasi-Greedy Approach Jiawei Zhang
10:15 AM
A Maiden Analysis of Longest Wait First Jeff Edmonds and Kirk Pruhs
10:40 AM
A Deterministic Nearly Linear-time Algorithm for Finding Minimum Cuts in Planar Graphs Parinya Chalermsook, Jittat Fakcharoenphol and Danupon Nanongkai
9C
 
 
 
 
9:00 AM
Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi and Dimitrios M. Thilikos
9:25 AM
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications Erik D. Demaine and Mohammad Taghi Hajiaghayi
9:50 AM
Hole and Antihole Detection in Graphs Stavros D. Nikolopoulos and Leonidas Palios
10:15 AM
Testing Bipartiteness of Geometric Intersection Graphs David Eppstein
10:40 AM
Finding Dominators Revisited Loukas Georgiadis and Robert E. Tarjan
Coffee Break
11:05 AM - 11:30 AM
 
 
  
Invited Plenary Session
11:30 AM - 12:30 PM
10
11:30 AM
How Random is the Human Genome? Peter Winkler, Bell Laboratories, Lucent Technologies
Lunch Break
12:30 PM - 2:00 PM
 
 
  
Concurrent Sessions
2:00 PM - 4:05 PM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
11A
 
 
 
 
2:00 PM
Complexities for Generalized Models of Self-Assembly Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao and Robert T. Schweller
2:25 PM
Invadable Self-Assembly: Combining Robustness with Efficiency Ho-Lin Chen, Qi Cheng, Ashish Goel, Ming-Deh Huang and
2:50 PM
On Contract and Refine Transformations Between Phylogenetic Trees Ganeshkumar Ganapathy, Vijaya Ramachandran and Tandy Warnow
3:15 PM
Reconstructing Strings from Random Traces Tugkan Batu, Sampath Kannan, Sanjeev Khanna and Andrew McGregor
3:40 PM
Improved Bounds on Sorting with Length-Weighted Reversals Michael Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Pinter, Steven Skiena and Firas Swidan
11B
 
 
 
 
2:00 PM
Point Containment in the Integer Hull of a Polyhedron Ernst Althaus
2:25 PM
Covering Minimum Spanning Trees of Random Subgraphs Michel X. Goemans and Jan Vondrak
2:50 PM
A Characterization of Easily Testable Induced Subgraphs Noga Alon and Asaf Shapira
3:15 PM
Bipartite Roots of Graphs Lap Chi Lau
3:40 PM
Two Tricks to Triangulate Chordal Probe Graphs in Polynomial Time A. Berry, M.C. Golumbic, and M. Lipshteyn
11C
 
 
 
 
2:00 PM
Non-migratory Online Deadline Scheduling on Multiprocessors Ho-Leung Chan, Tak-Wah Lam and Kar-Keung To
2:25 PM
The Maximum Latency of Selfish Routing Tim Roughgarden
2:50 PM
Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks T. Kimbrel and B. Schieber and M. Sviridenko
3:15 PM
The Wake-Up Problem in Multi-Hop Radio Networks Marek Chrobak, Leszek Gasieniec and Dariusz Kowalski
3:40 PM
A Fast Approximation Scheme for Fractional Covering Problems with Variable Upper Bounds Lisa Fleischer
Coffee Break
4:05 PM - 4:30 PM
 
 
  
Concurrent Sessions
4:30 PM - 6:35 PM
 
 
 
 
 
 
 
 
 
 
 
 
 
 
12A
 
 
 
 
4:30 PM
On Broadcasting in Heterogenous Networks Samir Khuller and Yoo Ah Kim
4:55PM
End-to-End Packet Scheduling in Wireless Ad Hoc Networks V.S. Anil Kumar, Madhav Marathe, Srinivasan Parthasarathy and Aravind Srinivasan
5:20 PM
Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels Matthew Andrews and Lisa Zhang
5:45 PM
Optimally Scheduling Movies-on-Demand to Minimize Delay When Server and Receiver Bandwidth May Differ William Evans and David Kirkpatrick
6:10 PM
Fair and Efficient Router Congestion Control Xiaojie Gao, Kamal Jain and Leonard J. Schulman
12B
 
 
 
 
4:30 PM
Randomized Pursuit-Evasion with Limited Visibility Volkan Isler, Sampath Kannan and Sanjeev Khanna
4:55PM
Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots Noa Agmon and David Peleg
5:20 PM
Approximate Classification via Earthmover Metrics Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar and Eva Tardos
5:45 PM
Facility Location with Service Installation Costs David Shmoys, Chaitanya Swamy and Retsef Levi
6:10 PM
On Finding a Guard that Sees Most and a Shop that Sells Most Otfried Cheong, Alon Efrat and Sariel Har-Peled
12C
 
 
 
 
4:30 PM
On the Diameter of the Symmetric Group: Polynomial Bounds Laszlo Babai, Robert Beals, Akos Seress
4:55PM
The Value of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups Cristopher Moore, Daniel Rockmore, Alexander Russell and Leonard Schulman
5:20 PM
Simultaneous Diophantine Approximation with Excluded Primes Laszlo Babai and Daniel Stefankovic
5:45 PM
Constructing Finite Field Extensions with Large Order Elements Qi Cheng
6:10 PM
Polynomial Interpolation from Multiples Joachim von zur Gathen and Igor Shparlinski

10/07/03