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 139 papers that were selected from a field of 454 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; Succinct Ordinal Trees with LevelAncestor Queries, Richard F. Geary, Rajeev Raman, and Venkatesh Raman; Compact Representations of Ordered Sets, Daniel K. Blandford and Guy E. Blelloch; Tight Bounds for the PartialSums Problem, Mihai Pǎtraşcu and Erik D. Demaine; The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables, Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal; Meldable RAM Priority Queues and Minimum Directed Spanning Trees, Ran Mendelson, Mikkel Thorup, and Uri Zwick; Finding a Long Directed Cycle, Harold N. Gabow and Shuxin Nie; A New Algorithm for Normal Dominance Constraints, Manuel Bodirsky, Denys Duchier, Joachim Niehren, and Sebastian Miele; RankMaximal Matchings, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna Paluch; Network Failure Detection and Graph Connectivity, Jon Kleinberg, Mark Sandler and Aleksandrs Slivkins; The Directed Circular Arrangement Problem, Joseph (Seffi) Naor and Roy Schwartz;Variable Length Path Coupling, Thomas P. Hayes and Eric Vigoda; Linear Phase Transition in Random Linear Constraint Satisfaction Problems, David Gamarnik; Quantitative Stochastic Parity Games, Krishnendu Chatterjee, Marcin Jurdziński, and Thomas A. Henzinger; On Distributions Computable by Random Walks on Graphs, Guy Kindler and Dan Romik; Exponential Bounds for DPLL below the Satisfiability Threshold, Dimitris Achlioptas, Paul Beame, and Michael Molloy; Who Says You Have to Look at the Input? The Brave New World of Sublinear Computing, Bernard Chazelle; Complexity Classification of Network Information Flow Problems, April Rasala Lehman and Eric Lehman; An Improved Data Stream Algorithm for Frequency Moments, Don Coppersmith and Ravi Kumar; Efficient Estimation Algorithms for Neighborhood Variance and Other Moments, Edith Cohen and Haim Kaplan; Optimal Space Lower Bounds for All Frequency Moments, David Woodruff; Optimal Routing in Chord, Prasanna Ganesan and Gurmeet Singh Manku; Approximation Schemes for Multidimensional Packing, José R. Correa and Claire Kenyon; New Approximability and Inapproximability Results for 2Dimensional Bin Packing, Nikhil Bansal and Maxim Sviridenko; On Rectangle Packing: Maximizing Benefits, Klaus Jansen and Guochuan Zhang; Optimal Online Bounded Space Multidimensional Packing, Leah Epstein and Rob van Stee; Windows Scheduling as a Restricted Version of Bin Packing, Amotz BarNoy, Richard E. Ladner, and Tami Tamir; Special Edges, and Approximating the Smallest Directed kedge Connected Spanning Subgraph, Harold N. Gabow On Colorings of Squares of Outerplanar Graphs, Geir Agnarsson and Magnús M. Halldórsson; Detecting Short Directed Cycles Using Rectangular Matrix Multiplication and Dynamic Programming Raphael Yuster and Uri Zwick; Approximating Minimum MaxStretch Spanning Trees on Unweighted Graphs, Yuval Emek and David Peleg; Approximate Distance Oracles for Unweighted Graphs in in Ő(n^2) Time, Surender Baswana and Sandeep Sen; Retroactive Data Structures, Erik D. Demaine, John Iacono, and Stefan Langerman; Proximity Mergesort: Optimal InPlace Sorting in the CacheOblivious Model, Gianni Franceschini; The Number of Bit Comparisons Used by Quicksort: An AverageCase Analysis, James Allen Fill and Svante Janson; Family Trees: An Ordered Dictionary with Optimal Congestion, Locality, Degree, and Search Time, Kevin C. Zatloukal and Nicholas J. A. Harvey; The Hyperring: A LowCongestion Deterministic Data Structure for Distributed Environments, Baruch Awerbuch and Christian Scheideler; Improved Upper Bounds for 3SAT, Kazuo Iwama and Suguru Tamaki; Locally Satisfiable Formulas, Daniel Král’; A Stronger Bound on Braess's Paradox, Henry Lin, Tim Roughgarden, and Éva Tardos; Multicommodity Facility Location, R. Ravi and A. Sinha; SRPT Optimally Utilizes Faster Machines to Minimize Flow Time, Jason McCullough and Eric Torng; A Faster Distributed Protocol for Constructing a Minimum Spanning Tree, Michael Elkin; Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms, Camil Demetrescu, Stefano Emiliozzi, and Giuseppe F. Italiano; Graph Decomposition and a Greedy Algorithm for EdgeDisjoint Paths, Kasturi Varadarajan and Ganesh Venkataraman; Models of Greedy Algorithms for Graph Problems, Sashka Davis and Russell Impagliazzo; The List Partition Problem for Graphs, Kathie Cameron, Elaine M. Eschen, Chính T. Hoŕng, and R. Sritharan; A Time Efficient Delaunay Refinement Algorithm, Gary L. Miller; AlmostDelaunay Simplices: Nearest Neighbor Relations for Imprecise Points, Deepak Bandyopadhyay and Jack Snoeyink; OutputSensitive Construction of the Union of Triangles, Eti Ezra and Micha Sharir; An Optimal Randomized Algorithm for Maximum Tukey Depth, Timothy M. Chan; Minimizing the Stabbing Number of Matchings, Trees, and Triangulations, Sándor P. Fekete, Marco E. Lübbecke, and Henk Meijer; Adaptive Sampling for Quickselect, Conrado Martinez, Daniel Panario, and Alfredo Viola; Fast Mixing for Independent Sets, Colorings and Other Models on Trees, Fabio Martinelli, Alistair Sinclair, and Dror Weitz; Slow Mixing of Glauber Dynamics for the Hardcore Model on the Hypercube, David Galvin and Prasad Tetali; Probabilistic Analysis of Knapsack Core Algorithms, Rene Beier and Berthold Vöcking; Torpid Mixing of Simulated Tempering on the Potts Model, Nayantara Bhatnagar and Dana Randall; Minimum Moment Steiner Trees, Wangqi Qiu and Weiping Shi; Approximation Schemes for Minimum 2EdgeConnected and Biconnected Subgraphs in Planar Graphs, Artur Czumaj, Michelangelo Grigni, Papa Sissokho, and Hairong Zhao; Approximation Schemes for Metric Bisection and Partitioning, W. Fernandez de la Vega, Marek Karpinski, and Claire Kenyon; 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; Correlation Clustering: Maximizing Agreements via Semidefinite Programming, Chaitanya Swamy; Quantum Computing, Raymond Laflamme; Interpolation Search for Nonindependent Data, Erik D. Demaine, Thouis Jones, and Mihai Pǎtraşcu; 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; Caching Queues in Memory Buffers, Rajeev Motwani and Dilys Thomas; LAND: Stretch (1 + ε) LocalityAware Networks for DHTs, Ittai Abraham, Dahlia Malkhi, and Oren Dobzinski; A Note on the Nearest Neighbor in GrowthRestricted Metrics, Kirsten Hildrum, John Kubiatowicz, Sean Ma, and Satish Rao; Buffer Minimization Using MaxColoring, Sriram V. Pemmaraju, Rajiv Raman, and Kasturi Varadarajan; On Minimizing the Total Flow Time on Multiple Machines, Nikhil Bansal; Nonindependent Randomized Rounding, Benjamin Doerr; A General Approach to Online Network Optimization Problems, Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph (Seffi) Naor; Approximate Local Search in Combinatorial Optimization, James B. Orlin, Abraham P. Punnen, and Andreas S. Schulz; Tradeoffs on the Location of the Core Node in a Network, JeanFrançois Macq and Michel X. Goemans; On the Convergence Time of a PathVector Protocol, Howard Karloff; Tabulation Based 4Universal Hashing with Applications to Second Moment Estimation, Mikkel Thorup and Yin Zhang; Approximate Budget Balanced Mechanisms with Low Communication Costs for the Multicast CostSharing Problem, Markus Bläser; Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?, Carlos Brito, Elias Koutsoupias, and Shailesh Vaya; When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications, Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter; Approximate Nearest Neighbor under Edit Distance via Product Metrics , Piotr Indyk; Fast Approximate Pattern Matching with Few Indels via Embeddings, Mihai Bădoiu and Piotr Indyk; Lyndon Words with a Fixed Standard Right Factor, Frédérique Bassino, Julien Clément, and Cyril Nicaud; Compression Boosting in Optimal Linear Time Using the BurrowsWheeler Transform, Paolo Ferragina and Giovanni Manzini; Dimension Reduction for Ultrametrics, Yair Bartal and Manor Mendel; Randomized kServer Algorithms for GrowthRate Bounded Graphs, Yair Bartal and Manor Mendel; The Pure Literal Rule Threshold and Cores in Random Hypergraphs, Michael Molloy; Efficient Algorithms for Bichromatic Separability, Pankaj K. Agarwal, Boris Aronov, and Vladlen Koltun; On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems, Nicole Immorlica, David Karger, Maria Minkoff, and Vahab S. Mirrokni; Frugality in Path Auctions, Edith Elkind, Amit Sahai, and Ken Steiglitz; An Exact SubexponentialTime Lattice Algorithm for Asian Options, TianShyr Dai and YuhDauh Lyuu; Structural and Algorithmic Aspects of Massive Social Networks, Stephen Eubank, V.S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan, and Nan Wang; A DeterminantBased Algorithm for Counting Matchings in a General Graph, Steve Chien; On the Number of Rectangular Partitions, Eyal Ackerman, Gill Barequet, and Ron Y. Pinter; Computing Equilibria for Congestion Games with (Im)perfect Information, Rene Beier, Artur Czumaj, Piotr Krysta, and Berthold Vöcking; Efficiently Decodable Codes Meeting GilbertVarshamov Bound for Low Rates, Venkatesan Guruswami and Piotr Indyk; Algorithms for Infinite HuffmanCodes, Mordecai J. Golin and Kin Keung Ma; A Certifying Algorithm for the ConsecutiveOnes Property, Ross M. McConnell; Generic Quantum Fourier Transforms, Cristopher Moore, Daniel Rockmore, and Alexander Russell; Quasiconvex Analysis of Backtracking Algorithms, David Eppstein; Navigating Nets: Simple Algorithms for Proximity Search, Robert Krauthgamer and James R. Leel Approximating the TwoLevel Facility Location Problem via a Quasigreedy Approach, Jiawei Zhang; A Maiden Analysis of Longest Wait First, Jeff Edmonds and Kirk Pruhs; A Deterministic NearLinear Time Algorithm for Finding Minimum Cuts in Planar Graphs, Parinya Chalermsook, Jittat Fakcharoenphol, and Danupon Nanongkai; Subexponential Parameterized Algorithms on Graphs of BoundedGenus and HMinorFree Graphs, Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos; Equivalence of Local Treewidth and Linear Local Treewidth and Its Algorithmic Applications Erik D. Demaine and MohammadTaghi Hajiaghayi; Hole and Antihole Detection in Graphs, Stavros D. Nikolopoulos and Leonidas Palios; Testing Bipartiteness of Geometric Intersection Graphs, David Eppstein; Finding Dominators Revisited, Loukas Georgiadis and Robert E. Tarjan; How Random Is the Human Genome?, Peter Winkler; Complexities for Generalized Models of SelfAssembly, Gagan Aggarwal, Michael H. Goldwasser, MingYang Kao, and Robert T. Schweller; Invadable SelfAssembly: Combining Robustness with Efficiency, HoLin Chen, Qi Cheng, Ashish Goel, MingDeh Huang, and Pablo Moisset de Espanés; On ContractandRefine Transformations between Phylogenetic Trees, Ganeshkumar Ganapathy, Vijaya Ramachandran, and Tandy Warnow; Reconstructing Strings from Random Traces, Tuğkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor; Improved Bounds on Sorting with LengthWeighted Reversals, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, and Firas Swidan; Point Containment in the Integer Hull of a Polyhedron, Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, and Kurt Mehlhorn; Covering Minimum Spanning Trees of Random Subgraphs, Michel X. Goemans and Jan Vondrák; A Characterization of Easily Testable Induced Subgraphs, Noga Alon and Asaf Shapira; Bipartite Roots of Graphs, Lap Chi Lau; Two Tricks to Triangulate Chordal Probe Graphs in Polynomial Time, Anne Berry, Martin Charles Golumbic, and Marina Lipshteyn; Nonmigratory Online Deadline Scheduling on Multiprocessors, HoLeung Chan, TakWah Lam, and KarKeung To; The Maximum Latency of Selfish Routing, Tim Roughgarden; Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks, Tracy Kimbrel, Baruch Schieber, and Maxim Sviridenko; The Wakeup Problem in Multihop Radio Networks, Marek Chrobak, Leszek Gaşieniec, and Dariusz Kowalski; A Fast Approximation Scheme for Fractional Covering Problems with Variable Upper Bounds Lisa Fleischer; On Broadcasting in Heterogenous Networks, Samir Khuller and YooAh Kim; EndtoEnd PacketScheduling in Wireless Adhoc Networks, V.S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan; Routing and Scheduling in Multihop Wireless Networks with TimeVarying Channels, Matthew Andrews and Lisa Zhang; Optimally Scheduling VideoonDemand to Minimize Delay When Server and Receiver Bandwidth May Differ, William Evans and David Kirkpatrick; Fair and Efficient Router Congestion Control, Xiaojie Gao, Kamal Jain, and Leonard J. Schulman; Randomized PursuitEvasion with Limited Visibility, Volkan Isler, Sampath Kannan, and Sanjeev Khanna; FaultTolerant Gathering Algorithms for Autonomous Mobile Robots, Noa Agmon and David Peleg; Approximate Classification via Earthmover Metrics, Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Éva Tardos; Facility Location with Service Installation Costs, David B. Shmoys, Chaitanya Swamy, and Retsef Levi; On Finding a Guard That Sees Most and a Shop That Sells Most, Otfried Cheong, Alon Efrat, and Sariel HarPeled; On the Diameter of the Symmetric Group: Polynomial Bounds, László Babai, Robert Beals, and Ákos Seress; The Power of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups, Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard J. Schulman; Simultaneous Diophantine Approximation with Excluded Primes, László Babai and Daniel Štefankovič; Constructing Finite Field Extensions with Large Order Elements, Qi Cheng; Polynomial Interpolation from Multiples, Joachim von zur Gathen and Igor E. Shparlinski; Author Index.
2004 / xvi + 1132 pages / Softcover / ISBN13: 9780898715583 / ISBN10: 089871558X / List Price $149.00 / SIAM Member Price $104.30 / Order Code PR114
