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.
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 /
List Price $180.50 / SIAM Member Price $126.35 / PR131