### Edited by Claire Mathieu
*Proceedings in Applied Mathematics 131*
The papers in this volume were presented at the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, held January 4-6, 2009, in New York, New York. 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.
**Contents** Preface and Acknowledgements; Improved Bounds and New Techniques for Daveport–Schinzel Sequences and Their Generalizations; Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs; The Ratio Index for Budgeted Learning, with Applications; Approximation Algorithms for Restless Bandit Problems; Better Algorithms for Benign Bandits; The Cover Time of Random Geometric Graphs; The Complexity of Simulating Brownian Motion; Sorting by Placement and Shift; Sampling Biased Lattice Configurations Using Exponential Metrics; On the Hitting Times of Quantum Versus Random Walks; Efficient Algorithms for the 2-Gathering Problem; Asymptotically Optimal Frugal Colouring; A Quadratic Kernel for Feedback Vertex Set; Coloring Triangle-Free Graphs on Surfaces; (Un)Expected Behavior of Digital Search Tree Profile; Combinatorial Stochastic Processes and Nonparametric Bayesian Modeling; Comparison-Based Time–Space Lower Bounds for Selection; Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings; Self-Overlapping Curves Revisited; Line Transversals of Convex Polyhedra in R3; Optimal Halfspace Range Reporting in Three Dimensions; Optimality of Belief Propagation for Random Assignment Problem; Termination Criteria for Solving Concurrent Safety and Reachability Games; An Efficient Sparse Regularity Concept; Almost All Hypergraphs without Fano Planes Are Bipartite; Hypergraph Regularity and Quasi-Randomness; Shortest Paths in Directed Planar Graphs with Negative Lengths: A Linear-Space O(n log2 n)-Time Algorithm; A Near-Linear Time Algorithm for Constructing a Cactus Representation of Minimum Cuts; Testing Halfspaces; Fast Edge Orientation for Unweighted Graphs; A Unified Approach to Distance-Two Colouring of Planar Graphs; Approximate Euclidean Shortest Paths amid Convex Obstacles; Approximate Line; Decomposition of Multiple Coverings into More Parts; On Stars and Steiner Stars. II; Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design; Computing the Nucleolus of Weighted Voting Games; High Rate Fingerprinting Codes and the Fingerprinting Capacity; On the Power of Two, Three and Four Probes; Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures; 3-Bit Dictator Testing: 1 vs. 5/8; Inserting a Vertex into a Planar Graph; Fast Algorithms for (max, min)-Matrix Multiplication and Bottleneck Shortest Paths; Sorting and Selection in Posets; Finding Duplicates in a Data Stream; Compressed Counting; Natural Algorithms; Maximal Biconnected Subgraphs of Random Planar Graphs; Approximate Shared-Memory Counting Despite a Strong Adversary; On Smoothes k-CNF Formulas and the Walksat Algorithm; Improved Smoothed Analysis of the k-Means Method; Pairing Heaps with O(log log n) Decrease Cost; A Simpler Implementation and Analysis of Chazelle’s Soft Heaps; Biased Range Trees; The Geometry of Binary Search Trees; Dual-Failure Distance and Connectivity Oracles; On the Maximum Quadratic Assignment Problem; Towards Computing the Grothendieck Constant; Approximating Submodular Functions Everywhere; Maximizing Submodular Set Functions Subject to Multiple Linear Constraints; Combinatorial Algorithms for Wireless Information Flow; Probability, Algorithms and Complexity; Generating Random Graphs with Large Girth; Expanders via Random Spanning Trees; The Extended k-Tree Algorithm; Sequential Cavity Method for Computing Limits of the Log-Partition Function for Lattice Models; A Universally Fastest Algorithms for Max 2-Sat, Max 2-CSP, and Everything in Between; Finding Shortest Contractible and Shortest Separating Cycles in Embedded Graphs; Cell Probe Lower Bounds for Succinct Data Structures; Succinct Geometric Indexes Supporting Point Location Queries; Exact Algorithms for Partial Curve Matching via the Fréchet Distance; String Hashing for Linear Probing; Parameterized Approximation Scheme for the Multiple Knapsack Problem; Improved Approximation Algorithms for Scheduling with Fixed Jobs; Scalably Scheduling Processes with Arbitrary Speedup Curves; Speed Scaling with an Arbitrary Power Function; A Logarithmic Approximation for Unsplittable Flow on Line Graphs; On the Complexity of Nash Equilibria of Action-Graph Games; How Hard Is It to Approximate the Best Nash Equilibrium?; Equilibria via Public Service Advertising; Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity; Equilibria of Atomic Flow Games Are not Unique; A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding; On the Bit-Complexity of Lempel–Ziv Compression; From Coding Theory to Efficient Pattern Matching; Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses; On Risks of Using Cuckoo Hashing with Simple Universal Hash Classes; Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location; Efficient Coordination Mechanisms for Unrelated Machine Scheduling; Clique-Width: On the Price of Generality; Reasoning about Online Algorithms with Weighted Automata; Appointment Scheduling with Discrete Random Durations; Hardness of Embedding Simplicial Complexes in Rd; Overcoming the ℓ1 Non-Embeddability Barrier: Algorithms for Product Metrics; On Low Dimensional Local Embeddings; The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, but Not Quite; Maximum Independent Set of Rectangles; Approximating Fractional Hypertree Width; An Almost O(log k)-Approximation for k-Connected Subgraphs; Improved Approximating Algorithms for Directed Steiner Forest; Transitive-Closure Spanners; Partitioning Graphs into Balanced Components; Efficient Algorithms on Sets of Permutations, Dominance, and Real-Weighted APSP; Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths; An Improved Approximation Algorithm for the Column Subset Selection Problem; Column Subset Selection, Matrix Factorization, and Eigenvalue Optimization; Loopless Generation of Multiset Permutations Using a Constant Number of Variables by Prefix Shifts; The Unreasonable Effectiveness of Martingales; Dimension Detection via Slivers; Persistent Homology for Kernels, Images, and Cokernels; Analysis of Scalar Fields over Point Cloud Data; Constructing Laplace Operator from Point Clouds in Rd; Size Complexity of Volume Meshes vs. Surface Meshes; Packing Mulitway Cuts in Capacitated Graphs; On the Approximability of Dodgson and Young Elections; Approximate Clustering without the Approximation; Robust PCA and Clustering in Noisy Mixtures; Coresets and Approximate Clustering for Bregman Divergences; Multi-Dimensional Online Tracking; A New Approach to Incremental Topological Ordering; Online Scheduling to Minimize the Maximum Delay Factor; Collecting Weighted Items from a Dynamic Queue; Paging and List Update under Bijective Analysis; Algorithms for Finding an Induced Cycle in Planar Graphs and Bounded Genus Graphs; List-Color-Critical Graphs on a Fixed Surface; Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs; Three-Coloring Triangle-Free Planar Graphs in Linear Time; A Nearly Linear Time Algorithms for the Half Integral Parity Disjoint Paths Packing Problem; The Uniform Hardcore Lemma via Approximate Bregman Projections; Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints; On the Approximability of the Maximum Feasible Subsystem Problem with 0/1-Coefficients; On the Relative Strength of Split, Triangle and Quadrilateral Cuts; A Simple Combinatorial Algorithm for Submodular Function Minimization; Weighted Flow Time Does not Admit O(1)-Competitive Algorithms; Secretary Problems: Weights and Discounts; Stream Sampling for Variance-Optimal Estimation of Subset Sums; An Online Mechanism for Ad Slot Reservations with Cancellations; Online Story Scheduling in Web Advertising.
2009 / 1284 page + index / CD / ISBN 978-0-898716-74-0 List Price $180.50 / SIAM Member Price $126.35 / **PR131** |