|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.
Preface; Acknowledgments; Dictionaries Using Variable-Length Keys and Data, with Applications, Daniel K. Blandford and Guy E. Blelloch; Lower Bounds on the Size of Selection and Rank Indexes, Peter Bro Miltersen; Dynamic Dictionary Matching and Compressed Suffix Trees, Ho-Leung Chan, Wing-Kai Hon, Tak-Wah Lam, andKunihiko Sadakane; A Categorization Theorem on Suffix Arrays with Applications to Space Efficient Text Indexes, Meng He, J. Ian Munro, and S. Srinivasa Rao; Towards a Complete Characterization of Tries, Gahyun Park and Wojciech Szpankowski; Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem, James Aspnes, Kevin Chang, and Aleksandr Yampolskiy; Marriage, Honesty, and Stability, Nicole Immorlica and Mohammad Mahdian; Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Production, Kamal Jain, Vijay V. Vazirani, and Yinyu Ye; On the Polynomial Time Computation of Equilibria for Certain Exchange Economies, Bruno Codenotti, Sriram Pemmaraju, and Kasturi Varadarajan; Computing Equilibria in Multi-Player Games, Christos H. Papadimitriouand Tim Roughgarden; On Distance Scales, Embeddings, and Efficient Relaxations of the Cut Cone, James R. Lee; Embeddings of Negative-Type Metrics and an Improved Approximation to Generalized Sparsest Cut, Shuchi Chawla, Anupam Gupta, and Harald Räcke; The Complexity of Low-Distortion Embeddings between Point Sets, Christos Papadimitriou and Shmuel Safra; Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces, Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos; A Tight Threshold for Metric Ramsey Phenomena, Moses Charikar and Adriana Karagiozova; The Interface between Computational and Combinatorial Geometry, Micha Sharir; Multiple-Source Shortest Paths in Planar Graphs, Philip N. Klein; Computing the Shortest Path: A* Search Meets Graph Theory, Andrew V. Goldberg and Chris Harrelson; Finding Large Cycles in Hamiltonian Graphs, Tomás Feder and Rajeev Motwani; Approximating Connectivity Augmentation Problems, Zeev Nutov; Primal-Dual Approach for Directed Vertex Connectivity Augmentation and Generalizations, László A. Végh and András A. Benczúr; Multidimensional Balanced Allocations, Andrei Broder and Michael Mitzenmacher; Online Client-Server Load Balancing without Global Information, Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert D. Kleinberg, and Tom Leighton; Job Shop Scheduling with Unit Processing Times, Nikhil Bansal, Tracy Kimbrel, and Maxim Sviridenko; Approximating the Average Response Time in Broadcast Scheduling, Nikhil Bansal, Moses Charikar, Sanjeev Khanna, and Joseph (Seffi) Naor; Improved Schedule for Radio Broadcast, Michael Elkin and Guy Kortsarz; On Levels in Arrangements of Surfaces in Three Dimensions, Timothy M. Chan; Distributions of Points in the Unit-Square and Large k-Gons, Hanno Lefmann; On Geometric Permutations Induced by Lines Transversal through a Fixed Point, Boris Aronov and Shakhar Smorodinsky; Subgradient and Sampling Algorithms for l1 Regression, Kenneth L. Clarkson; Approximation Hardness of Optimization Problems in Intersection Graphs of d-Dimensional Boxes, Miroslav Chlebík and Janka Chlebíková; Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs, Robert D. Kleinberg and Jon M. Kleinberg; Adversarial Deletion in a Scale Free Random Graph Process, Abraham D. Flaxman, Alan M. Frieze, and Juan Vera; The Influence of Search Engines on Preferential Attachment, Soumen Chakrabarti, Alan Frieze, and Juan Vera; On the Spread of Viruses on the Internet, Noam Berger, Christian Borgs, Jennifer T. Chayes, and Amin Saberi; Analyzing and Characterizing Small-World Graphs, Van Nguyen and Chip Martel; Substring Compression Problems, Graham Cormode and S. Muthukrishnan; Optimizing Markov Models with Applications to Triangular Connectivity Coding, Stefan Gumhold; Dotted Interval Graphs and High Throughput Genotyping, Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, and Zohar Yakhini; Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network, Jesper Jansson, Nguyen Bao Nguyen, and Wing-Kin Sung; Unknotting is in AM ∩ co-AM, Masao Hara, Seiichi Tani, and Makoto Yamamoto; A Constant Approximation Algorithm for the One-Warehouse Multi-Retailer Problem, Retsef Levi, Robin O. Roundy, and David B. Shmoys; Sharing the Cost More Efficiently: Improved Approximation for Multicommodity Rent-or-Buy, Luca Becchetti, Jochen Könemann, Stefano Leonardi, and M. Pál; Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient, Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan; Adaptivity and Approximation for Stochastic Packing Problems, Brian C. Dean, Michel X. Goemans, and Jan Vondrák; Theory of Semidefinite Programming for Sensor Network Localization, Anthony Man-Cho So and Yinyu Ye; An O(VE) Algorithm for Ear Decompositions of Matching-Covered Graphs, Marcelo H. de Carvalho and Joseph Cheriyan; Popular Matchings, David J. Abraham, Robert W. Irving, Telikepalli Kavitha, and Kurt Mehlhorn; Dominator Tree Verification and Vertex-Disjoint Paths, Loukas Georgiadis and Robert E. Tarjan; Online Topological Ordering, Irit Katriel and Hans L. Bodlaender; All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs, David Eppstein; LP Decoding Achieves Capacity, Jon Feldman and Cliff Stein; Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-Hard, Venkatesan Guruswami and Alexander Vardy; Collecting Correlated Information from a Sensor Network, Micah Adler; Deterministic Network Coding by Matrix Completion, Nicholas J. A. Harvey, David R. Karger, and Kazuo Murota; Network Coding: Does the Model Need Tuning?, April Rasala Lehman and Eric Lehman; Pianos Are Not Flat: Rigid Motion Planning in Three Dimensions, Vladlen Koltun; A Constant-Factor Approximation Algorithm for Optimal Terrain Guarding, Boaz Ben-Moshe, Matthew J. Katz, and Joseph S. B. Mitchell; Ray Shooting amid Balls, Farthest Point from a Line, and Range Emptiness Searching, Micha Sharir and Hayim Shaul; Space-Time Tradeoffs for Approximate Spherical Range Counting, Sunil Arya, Theocharis Malamatos, and David M. Mount; Online Conflict-Free Coloring for Intervals, Amos Fiat, Meital Levy, Jiří Matouek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl; Loop Quantum Gravity, John Baez; Approximation Algorithms for Cycle Packing Problems, Michael Krivelevich, Zeev Nutov, and Raphael Yuster; Approximating the Smallest k-edge Connected Spanning Subgraph by LP-Rounding, Harold N. Gabow, Michel X. Goemans, Éva Tardos, and David P. Williamson; Partial Covering of Hypergraphs, Özgür Sümer; Approximating Vertex Cover on Dense Graphs, Tomokazu Imamura and Kazuo Iwama; Bidimensionality: New Connections between FPT Algorithms and PTASs, Erik D. Demaine and MohammadTaghi Hajiaghayi; Limitations of Cross-Monotonic Cost Sharing Schemes, Nicole Immorlica, Mohammad Mahdian, and Vahab S. Mirrokni; A Group-Strategyproof Mechanism for Steiner Forests, Jochen Könemann, Stefano Leonardi, and Guido Schäfer; Collusion-Resistant Mechanisms for Single-Parameter Agents, Andrew V. Goldberg and Jason D. Hartline; A Multiple-Choice Secretary Algorithm with Applications to Online Auctions, Robert Kleinberg; Rounds vs. Queries Trade-off in Noisy Computation, Navin Goyal and Michael Saks; Distributed Approaches to Triangulation and Embedding, Aleksandrs Slivkins; Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics, Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos; Sparse Source-wise and Pair-wise Distance Preservers, Don Coppersmith and Michael Elkin; Lower Bound for Sparse Euclidean Spanners, Pankaj K. Agarwal, Yusu Wang, and Peng Yin; New Constructions of (α,β)-Spanners and Purely Additive Spanners, Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie; Graphs Excluding a Fixed Minor Have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality, Erik D. Demaine and MohammadTaghi Hajiaghayi; Dissections and Trees, with Applications to Optimal Mesh Encoding and to Random Sampling, Éric Fusy, Dominique Poulalhon, and Gilles Schaeffer; The Expected Value of Random Minimal Length Spanning Tree of a Complete Graph, David Gamarnik; Girth Restrictions for the 5-Flow Conjecture, Martin Kochol; Linear Equations, Arithmetic Progressions and Hypergraph Property Testing, Noga Alon and Asaf Shapira; The Relative Worst Order Ratio Applied to Paging, Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen; Strictly Convex Drawings of Planar Graphs, Günter Rote; External-Memory Exact and Approximate All-Pairs Shortest-Paths in Undirected Graphs, Rezaul Alam Chowdhury and Vijaya Ramachandran; Graph Distances in the Streaming Model: The Value of Space, Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang; Lower Bounds for External Algebraic Decision Trees, Jeff Erickson; On Hierarchical Routing in Doubling Metrics, Hubert T-H. Chan, Anupam Gupta,Bruce M. Maggs, and Shuheng Zhou; Fast Convergence of Selfish Rerouting, Eyal Even-Dar and Yishay Mansour; Oblivious Routing on Node-Capacitated and Directed Graphs, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, and Harald Räcke; Distributed Online Call Control on General Networks, Harald Räcke and Adi Rosén; An Optimal Online Algorithm for Packet Scheduling with Agreeable Deadlines, Fei Li, Jay Sethuraman, and Clifford Stein; An Optimal Dynamic Interval Stabbing-Max Data Structure?, Pankaj K. Agarwal, Lars Arge, and Ke Yi; Self-Adjusting Top Trees, Robert E. Tarjan and Renato F. Werneck; An Optimal Bloom Filter Replacement, Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao; Efficient Hashing with Lookups in Two Memory Accesses, Rina Panigrahy; Improved Range-Summable Random Variable Construction Algorithms, A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan, and M. Strauss; A Spectral Heuristic for Bisecting Random Graphs, Amin Coja-Oghlan; Complete Partitions of Graphs, Guy Kortsarz, Jaikumar Radhakrishnan, and Sivaramakrishnan Sivasubramanian; Two Algorithms for General List Matrix Partitions, Tomás Feder, Pavol Hell, Daniel Král, and Jiří Sgall; How Fast is the k-Means Method?, Sariel Har-Peled and Bardia Sadri; On Approximating the Depth and Related Problems, Boris Aronov and Sariel Har-Peled; Multicoloring Unit Disk Graphs on Triangular Lattice Points, Yuichiro Miyamoto and Tomomi Matsui; An Asymptotic Approximation Scheme for Multigraph Edge Coloring, Peter Sanders and David Steurer; Computing Minimal Triangulations in Time O(nα log n) = o(n2.376), Pinar Heggernes, Jan Arne Telle, and Yngve Villanger; Finding the Shortest Bottleneck Edge in a Parametric Minimum Spanning Tree, Timothy M. Chan; On the Random 2-Stage Minimum Spanning Tree, Abraham D. Flaxman, Alan Frieze, and Michael Krivelevich; Rigorous Analysis of Heuristics for NP-Hard Problems, Uriel Feige; An Improved Approximation Algorithm for Virtual Private Network Design, Friedrich Eisenbrand and Fabrizio Grandoni; Network Design for Information Networks, Ara Hayrapetyan, Chaitanya Swamy, and Éva Tardos; On the Approximability of Some Network Design Problems, Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor, and Amitabh Sinha; Approximating k-Median with Non-uniform Capacities, Julia Chuzhoy and Yuval Rabani; Improved Approximation for Universal Facility Location, Naveen Garg, Rohit Khandekar, and Vinayaka Pandit; The Cover Time of Two Classes of Random Graphs, Colin Cooper and Alan Frieze; Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets, Tom Hayes and Eric Vigoda; Sampling Regular Graphs and a Peer-to-Peer Network, Colin Cooper, Martin Dyer, and Catherine Greenhill; The Bin-Covering Technique for Thresholding Random Geometric Graph Properties, S. Muthukrishnan and Gopal Pandurangan; Random Planar Graphs with n Nodes and a Fixed Number of Edges, Stefanie Gerke, Colin McDiarmid, Angelika Steger, and Andreas Weißl; Provably Good Moving Least Squares, Ravikrishna Kolluri; Manifold Reconstruction from Point Samples, Siu-Wing Cheng,Tamal K. Dey, and Edgar A. Ramos; Delaunay Triangulations Approximate Anchor Hulls, Tamal K. Dey, Joachim Giesen, and Samrat Goswami; Greedy Optimal Homotopy and Homology Generators, Jeff Erickson and Kim Whittlesey; Controlled Perturbation for Delaunay Triangulations, Stefan Funke, Christian Klein, Kurt Mehlhorn, and Susanne Schmitt; Near-Independence of Permutations and an Almost Sure Polynomial Bound on the Diameter of the Symmetric Group, László Babai and Thomas P. Hayes; Matrix Rounding with Low Error in Small Submatrices, Benjamin Doerr; Can the TPR1 Structure Help Us to Solve the Algebraic Eigenproblem?, Victor Y. Pan; Optimal Random Number Generation from a Biased Coin, Sung-il Pae and Michael C. Loui; A New Look at Survey Propagation and Its Generalizations, Elitza Maneva, Elchanan Mossel, and Martin J. Wainwright; Coins Make Quantum Walks Faster, Andris Ambainis, Julia Kempe, and Alexander Rivosh; Quantum Algorithms for the Triangle Problem, Frédéric Magniez, Miklos Santha, and Mario Szegedy; The Hidden Subgroup Problem and Permutation Group Theory, Julia Kempe and Aner Shalev; Testing Hierarchical Systems, Damon Mosk-Aoyama and Mihalis Yannakakis; Conformance Testing in the Presence of Multiple Faults, Viraj Kumar and Mahesh Viswanathan; Online Ascending Auctions for Gradually Expiring Items, Ron Lavi and Noam Nisan; Near-Optimal Online Auctions, Avrim Blum and Jason D. Hartline; On Profit-Maximizing Envy-Free Pricing, Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry; Improved Recommendation Systems, Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle; Selfish Routing with Atomic Players, Tim Roughgarden; Author Index
2005 / 1204 pages / Softcover / ISBN-13: 978-0-898715-85-9 / ISBN-10: 0-89871-585-7 /
List Price $139.00 / SIAM Member Price $97.30 / Order Code PR118