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; online 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.
Contents
Preface; Acknowledgments; Dictionaries Using VariableLength 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, HoLeung Chan, WingKai Hon, TakWah 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 SumofSquares Partition Problem, James Aspnes, Kevin Chang, and Aleksandr Yampolskiy; Marriage, Honesty, and Stability, Nicole Immorlica and Mohammad Mahdian; Market Equilibria for Homothetic, QuasiConcave 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 MultiPlayer Games, Christos H. Papadimitriouand Tim Roughgarden; On Distance Scales, Embeddings, and Efficient Relaxations of the Cut Cone, James R. Lee; Embeddings of NegativeType Metrics and an Improved Approximation to Generalized Sparsest Cut, Shuchi Chawla, Anupam Gupta, and Harald Räcke; The Complexity of LowDistortion Embeddings between Point Sets, Christos Papadimitriou and Shmuel Safra; Approximation Algorithms for LowDistortion Embeddings into LowDimensional 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; MultipleSource 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; PrimalDual 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 ClientServer 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 UnitSquare and Large kGons, 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 dDimensional Boxes, Miroslav Chlebík and Janka Chlebíková; Isomorphism and Embedding Problems for Infinite Limits of ScaleFree 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 SmallWorld 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 WingKin Sung; Unknotting is in AM ∩ coAM, Masao Hara, Seiichi Tani, and Makoto Yamamoto; A Constant Approximation Algorithm for the OneWarehouse MultiRetailer Problem, Retsef Levi, Robin O. Roundy, and David B. Shmoys; Sharing the Cost More Efficiently: Improved Approximation for Multicommodity RentorBuy, 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 ManCho So and Yinyu Ye; An O(VE) Algorithm for Ear Decompositions of MatchingCovered 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 VertexDisjoint 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; MaximumLikelihood Decoding of ReedSolomon Codes is NPHard, 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 ConstantFactor Approximation Algorithm for Optimal Terrain Guarding, Boaz BenMoshe, 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; SpaceTime Tradeoffs for Approximate Spherical Range Counting, Sunil Arya, Theocharis Malamatos, and David M. Mount; Online ConflictFree 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 kedge Connected Spanning Subgraph by LPRounding, 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 CrossMonotonic Cost Sharing Schemes, Nicole Immorlica, Mohammad Mahdian, and Vahab S. Mirrokni; A GroupStrategyproof Mechanism for Steiner Forests, Jochen Könemann, Stefano Leonardi, and Guido Schäfer; CollusionResistant Mechanisms for SingleParameter Agents, Andrew V. Goldberg and Jason D. Hartline; A MultipleChoice Secretary Algorithm with Applications to Online Auctions, Robert Kleinberg; Rounds vs. Queries Tradeoff 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 FarachColton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos; Sparse Sourcewise and Pairwise 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 5Flow 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; ExternalMemory Exact and Approximate AllPairs ShortestPaths 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 TH. Chan, Anupam Gupta,Bruce M. Maggs, and Shuheng Zhou; Fast Convergence of Selfish Rerouting, Eyal EvenDar and Yishay Mansour; Oblivious Routing on NodeCapacitated 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 StabbingMax Data Structure?, Pankaj K. Agarwal, Lars Arge, and Ke Yi; SelfAdjusting 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 RangeSummable Random Variable Construction Algorithms, A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan, and M. Strauss; A Spectral Heuristic for Bisecting Random Graphs, Amin CojaOghlan; 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 kMeans Method?, Sariel HarPeled and Bardia Sadri; On Approximating the Depth and Related Problems, Boris Aronov and Sariel HarPeled; 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 2Stage Minimum Spanning Tree, Abraham D. Flaxman, Alan Frieze, and Michael Krivelevich; Rigorous Analysis of Heuristics for NPHard 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 kMedian with Nonuniform 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 PeertoPeer Network, Colin Cooper, Martin Dyer, and Catherine Greenhill; The BinCovering 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, SiuWing 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; NearIndependence 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, Sungil 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 MoskAoyama 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; NearOptimal Online Auctions, Avrim Blum and Jason D. Hartline; On ProfitMaximizing EnvyFree Pricing, Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry; Improved Recommendation Systems, Baruch Awerbuch, Boaz PattShamir, David Peleg, and Mark Tuttle; Selfish Routing with Atomic Players, Tim Roughgarden; Author Index
2005 / 1204 pages / Softcover / ISBN13: 9780898715859 / ISBN10: 0898715857 / List Price $139.00 / SIAM Member Price $97.30 / Order Code PR118
