
2009 / 1284 page + index / CD / ISBN: 9780898716740 / List Price $186.00 / SIAM Member Price $130.20 / PR131
The papers in this volume were presented at the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, held January 46, 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 2Gathering Problem; Asymptotically Optimal Frugal Colouring; A Quadratic Kernel for Feedback Vertex Set; Coloring TriangleFree Graphs on Surfaces; (Un)Expected Behavior of Digital Search Tree Profile; Combinatorial Stochastic Processes and Nonparametric Bayesian Modeling; ComparisonBased Time–Space Lower Bounds for Selection; LinearTime Algorithms for Geometric Graphs with Sublinearly Many Crossings; SelfOverlapping 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 QuasiRandomness; Shortest Paths in Directed Planar Graphs with Negative Lengths: A LinearSpace O(n log2 n)Time Algorithm; A NearLinear Time Algorithm for Constructing a Cactus Representation of Minimum Cuts; Testing Halfspaces; Fast Edge Orientation for Unweighted Graphs; A Unified Approach to DistanceTwo 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, NearDuplicates and SmallWorld 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 TreeLike Lovász–Schrijver Procedures; 3Bit 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 SharedMemory Counting Despite a Strong Adversary; On Smoothes kCNF Formulas and the Walksat Algorithm; Improved Smoothed Analysis of the kMeans 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; DualFailure 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 kTree Algorithm; Sequential Cavity Method for Computing Limits of the LogPartition Function for Lattice Models; A Universally Fastest Algorithms for Max 2Sat, Max 2CSP, 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 ActionGraph 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 TopDown DynamicProgramming Approach to PrefixFree Coding; On the BitComplexity 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 HardCapacitated Facility Location; Efficient Coordination Mechanisms for Unrelated Machine Scheduling; CliqueWidth: 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 NonEmbeddability 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 kConnected Subgraphs; Improved Approximating Algorithms for Directed Steiner Forest; TransitiveClosure Spanners; Partitioning Graphs into Balanced Components; Efficient Algorithms on Sets of Permutations, Dominance, and RealWeighted APSP; Discounted Deterministic Markov Decision Processes and Discounted AllPairs 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; MultiDimensional 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; ListColorCritical Graphs on a Fixed Surface; Additive Approximation Algorithms for ListColoring MinorClosed Class of Graphs; ThreeColoring TriangleFree 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/1Coefficients; 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 VarianceOptimal Estimation of Subset Sums; An Online Mechanism for Ad Slot Reservations with Cancellations; Online Story Scheduling in Web Advertising.
ISBN: 9780898716740