Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms

the SIAM Activity Group0898715857, 9780898715859

Symposium held in Vancouver, British Columbia, January 2005.
The Symposium was jointly sponsored by the SIAM Activity Group on Discrete Mathematics and by SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory.
This volume contains 136 papers that were selected from a field of 491 submissions based on their originality, technical contribution, and relevance. The symposium and the papers focus on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations.
Themes and application areas come primarily from Computer Science and Discrete Mathematics, but also include other areas of application areas such as Biology, Physics and Finance. Specific areas include, but are not limited to: discrete mathematics and combinatorics; combinatorial structures; communication networks; computational biology; computational physics; computational finance; computational geometry; computer graphics and computer vision; computer systems; cryptography and security; databases and information retrieval; discrete optimization; discrete probability; distributed algorithms; experimental algorithmics; graph drawing; graphs and networks; machine learning; mathematical programming; molecular computing; number theory and algebra; on-line problems; pattern matching and data compression; quantum computing; random structures; robotics; statistical inference; and symbolic computation.
Although the papers were not formally refereed, every attempt was made to verify the main claims. Extended versions of many of these papers may appear later in more polished form in various scientific journals.

---

Table of contents :
PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS……Page 1
CONTENTS……Page 4
PREFACE……Page 14
ACKNOWLEDGMENTS……Page 15
Session 1A Dictionaries Using Variable-Length Keys and Data, with Applications……Page 18
Session 1B Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem……Page 60
Session 1C On distance scales, embeddings,and efficient relaxations of the cut cone……Page 109
Session 2 The Interface Between Computational and Combinatorial Geometry……Page 154
Session 3A Multiple-source shortest paths in planar graphs……Page 163
Session 3B Multidimensional Balanced Allocations……Page 212
Session 3C On Levels in Arrangements of Surfaces in Three Dimensions……Page 249
Session 4A Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs……Page 294
Session 4B Substring Compression Problems……Page 338
Session 4C A Constant Approximation Algorithm for the One-Warehouse Multi-Retailer Problem……Page 382
Session 5A An O(VE) Algorithm for Ear Decompositions of Matching-Covered Graphs……Page 432
Session 5B LP Decoding Achieves Capacity……Page 477
Session 5C Pianos are not Flat:Rigid Motion Planning in Three Dimensions……Page 522
Session 6 INVITED PLENARY ABSTRACT……Page 572
Session 7A Approximation Algorithms for Cycle Packing Problems……Page 573
Session 7B Limitations of cross-monotonic cost sharing schemes……Page 619
Session 7C Distributed Approaches to Triangulation and Embedding……Page 657
Session 8A Graphs Excluding a Fixed Minor have Grids as Large as Treewidth,with Combinatorial and Algorithmic Applications through Bidimensionality……Page 699
Session 8B The Relative Worst Order Ratio Applied to Paging……Page 735
Session 8C On Hierarchical Routing in Doubling Metrics……Page 779
Session 9A An Optimal Dynamic Interval Stabbing-Max Data Structure……Page 820
Session 9B A Spectral Heuristic for Bisecting Random Graphs……Page 867
Session 9C Multicoloring Unit Disk Graphs on Triangular Lattice Points……Page 912
Session 10 INVITED PLENARY ABSTRACT……Page 944
Session 11A An Improved Approximation Algorithm for Virtual Private Network Design……Page 945
Session 11B The cover time of two classes of random graphs……Page 978
Session 11C Provably Good Moving Least Squares……Page 1025
Session 12A Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group……Page 1074
Session 12B Coins Make Quantum Walks Faster……Page 1116
Session 12C Online Ascending Auctions for Gradually Expiring Items……Page 1163
AUTHOR INDEX……Page 1204