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:
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 RAcke; 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 BA[pound]doiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald RAcke, 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, TomAis Feder and Rajeev Motwani; Approximating Connectivity Augmentation Problems, Zeev Nutov; Primal-Dual Approach for Directed Vertex Connectivity Augmentation and Generalizations, LAiszlA3 A. VA[copyright]gh and AndrAis A. BenczA[degrees]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 I1 Regression, Kenneth L. Clarkson; Approximation Hardness of Optimization Problems in Intersection Graphs of d-Dimensional Boxes, Miroslav ChlebA-k and Janka ChlebA-kovAi; 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 n 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 KAnemann, Stefano Leonardi, and M. PAil; 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 VondrAik; 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, Viadien 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, JiA A-MatouAjek, Elchanan Mossel, JAjnos 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, Ava Tardos, and David P. Williamson; Partial Covering of Hypergraphs, A-zgA 1/4 r SA 1/4 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 KAnemann, Stefano Leonardi, and Guido SchAfer; 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 BA[pound]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 (Ai,A)-Spanners and Purely Additive Spanners, Surender Baswana, Telikep