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
|
|
Registration Open 8:00 AM - 6:30 PM |
|
|||
ACM - SIAM SODA Welcome Reception
6:00 PM - 8:00 PM |
||||||
11-Jan-04
|
|
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
|
|
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
|
|
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