Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
Published in 2010
Book
XVIII, 1667 pages
978-0-89871-701-3 (ISBN)
Description
The papers in this volume were presented at the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, held January 17-19, 2010, in Austin, TX. 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.
More details
Content
Preface; On the Optimality of Spiral Search; An Improved Competitive Algorithm for Reordering Buffer Management; How to Meet Asynchronously (Almost) Everywhere; A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model; Towards the Randomized k-Server Conjecture: A Primal-Dual Approach; Testing Monotone Continuous Distributions on High-dimensional Real Cubes; Property Testing and Parameter Testing for Permutations; Near-Optimal Sublinear Time Algorithms for Ulam Distance; Lower Bounds for Testing Triangle-freeness in Boolean Functions;
Counting Stars and Other Small Subgraphs in Sublinear Time; Cell-Probe Lower Bounds for Succinct Partial Sums; On the Cell Probe Complexity of Dynamic Membership; Fully-Functional Succinct Trees; Data Structures for Range Minimum Queries in Multidimensional Arrays; Counting Inversions, Offline Orthogonal Range Counting, and Related Problems; Differential Privacy in New Settings;
Lower Bounds for Edit Distance and Produce Metrics via Poincaré-Type Inequalities; Genus and the Geometry of the Cut Graph; Testing Planarity of Partially Embedded Graphs; Inapproximability for Planar Embedding Problems; Towards a Calculus for Non-Linear Spectral Gaps; A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics; PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs; Belief Propagation for Min-cost Network Flow: Convergence & Correctness; Finding the Jaccard Median; The Focus of Attention Problem; Recognizing a Totally Odd K4-subdivision, Parity 2-disjoint Rooted Paths and a Parity Cycle Through Specified Elements; Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs; The Edge Disjoint Paths Problem with Eulerian Graphs and 4-edge-connected Graphs; On Bramble, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic; An (almost) Linear Time Algorithms for Odd Cyles Transversal; An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem; A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing; Region Growing for Multi-Route Cuts; Asymmetric Traveling Salesman Path and Directed Latency Problems; Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls; Quantum Algorithms for Highly Non-Linear Boolean Functions; Compact Ancestry Labeling Schemes for XML Trees; Generating a d-dimensional Linear Subspace Efficiently; Algorithms for Ray Class Groups and Hilbert Class Fields; A Space-Time Tradeoff for Permutation Problems; Algorithmic Lower Bounds for Problems Parameterized with Clique-Width; Bidimensionality and Kernels; Solving MAX-r-SAT Above a Tight Lower Bound; Inapproximability for BCG-Based Combinatorial Auctions; Price of Anarchy for Greedy Auctions; Incentive Compatible Budget Elicitation in Multi-unit Auctions; Utilitarian Mechanism Design for Multi-Objective Optimization; Pricing Randomized Allocations; Universal ?-approximators for Integrals; Optimally Reconstructing Weighted Graphs Using Queries; Online Learning with Queries; Coresets and Sketches for High Dimensional Subspace Approximation Problems; Convergence, Stability, and Discrete Approximation of Laplace Spectra; Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities; Fast SDP Algorithms for Constraint Satisfaction Problems; Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications; Correlation Clustering with Noisy Input; A Polynomial Time Approximation Scheme for k-Consensus Clustering; Google's Auction for TV Ads; A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs; Solving the Replacement Paths Problem for Planar Directed Graphs in O (n log n) Time; Bounding Variance and Expectation of Longest Path Lengths in DAGs; Highway Dimension, Shortest Paths, and Provably Efficient Algorithms; Maximum Flows and Parametric Shortest Paths in Planar Graphs; On the Equilibria of Alternating Move Games; Monotonicity in Bargaining Networks; Sharp Dichotomies for Regret Minimization in Metric Spaces; Solving Simple Stochastic Tail Games; One-Counter Markov Decision Processes; On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture; An Improved Construction of Progression-Free Sets; Geometric Optimization and Sums of Algebraic Functions; Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface; How Far Can You Reach?; A Model of Computation for MapReduce; Synchrony and Asynchrony in Neural Networks; Distributed Agreement with Optimal Communication Complexity; How Good is the Chord Algorithm?; Deterministic Algorithms for the Lovász Local Lemma; A Deterministic Truthful PTAS for Scheduling Related Machines; A Fourier Space Algorithm for Solving Quadratic Assignment Problems; EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard; Reconstructing Approximate Phylogenetic Trees from Quartet Samples; Shape Replication through Self-Assembly and RNase Enzymes; On the Possibility of Faster SAT Algorithms; Paired Approximation Problems and Incompatible Inapproximabilities; Correlation Robust Stochastic Optimization; Approximability of Robust Network Design; Differentially Private Combinatorial Optimization; Efficiently Decodable Non-adaptive Group Testing; 1-Pass Relative-Error Lp-Sampling with Applications; On the Exact Space Complexity of Sketching and Streaming Small Norms; A Locality-Sensitive Hash for Real Vectors; Lower Bounds for Sparse Recovery; Flow-Cut Gaps for Integer and Fractional Multiflows; A Max-Flow/Min-Cut Algorithms for a Class of Wireless Networks; Testing Additive Integrality Gaps; Classified Stable Matching; Basis Reduction and the Complexity of Brand-and-Bound; Randomized Shellsort: A Simple Oblivious Sorting Algorithm; Data-Specific Analysis of String Sorting; Fast Distance Multiplication of Unit-Monge Matrices; Regular Expression Matching with Multi-Strings and Intervals; Road Network Reconstruction for Organizing Paths; The Power of Convex Relaxation: The Surprising Stories of Matrix Completion and Compressed Sensing; An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling; Resource Minimization for Fire Containment; Algorithms and Complexity for Periodic Real-Time Scheduling; Energy Efficient Scheduling via Partial ShutdownSPRT is 1.86-Competitive for Completion Time Scheduling; The Rank of Diluted Random Graphs; The Scaling Window for a Random Graph with a Given Degree Sequence; Efficient Broadcast on Random Geometric Graphs; Speeding Up Random Walks with Neighborhood Exploration; Vertices of Degree k in Random Maps; Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs; Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures; Faster Exponential Time Algorithms for the Shortest Vector Problem; Streaming Algorithms for Extent Problems in High Dimensions; Deletion Without Rebalancing in Balanced Binary Trees; On Linear and Semidefinite Programming Relaxations for Hypergraph Matching; Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph; Tree Embeddings for Two-Edge-Connected Network Design; A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover; Self-improving Algorithms for Convex Hulls; The Forest Hiding Problem; Terrain Guarding is NP-Hard; Hardness Results for Homology Localization; Orthogonal Ham-Sandwich Theorem in R3; The (1 + ?)-Choice Process and Weighted Balls-into-Bins; Quasirandom Load Balancing; Thim Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Start Shaped Bodies; Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees; Rumour Spreading and Graph Conductance
Counting Stars and Other Small Subgraphs in Sublinear Time; Cell-Probe Lower Bounds for Succinct Partial Sums; On the Cell Probe Complexity of Dynamic Membership; Fully-Functional Succinct Trees; Data Structures for Range Minimum Queries in Multidimensional Arrays; Counting Inversions, Offline Orthogonal Range Counting, and Related Problems; Differential Privacy in New Settings;
Lower Bounds for Edit Distance and Produce Metrics via Poincaré-Type Inequalities; Genus and the Geometry of the Cut Graph; Testing Planarity of Partially Embedded Graphs; Inapproximability for Planar Embedding Problems; Towards a Calculus for Non-Linear Spectral Gaps; A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics; PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs; Belief Propagation for Min-cost Network Flow: Convergence & Correctness; Finding the Jaccard Median; The Focus of Attention Problem; Recognizing a Totally Odd K4-subdivision, Parity 2-disjoint Rooted Paths and a Parity Cycle Through Specified Elements; Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs; The Edge Disjoint Paths Problem with Eulerian Graphs and 4-edge-connected Graphs; On Bramble, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic; An (almost) Linear Time Algorithms for Odd Cyles Transversal; An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem; A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing; Region Growing for Multi-Route Cuts; Asymmetric Traveling Salesman Path and Directed Latency Problems; Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls; Quantum Algorithms for Highly Non-Linear Boolean Functions; Compact Ancestry Labeling Schemes for XML Trees; Generating a d-dimensional Linear Subspace Efficiently; Algorithms for Ray Class Groups and Hilbert Class Fields; A Space-Time Tradeoff for Permutation Problems; Algorithmic Lower Bounds for Problems Parameterized with Clique-Width; Bidimensionality and Kernels; Solving MAX-r-SAT Above a Tight Lower Bound; Inapproximability for BCG-Based Combinatorial Auctions; Price of Anarchy for Greedy Auctions; Incentive Compatible Budget Elicitation in Multi-unit Auctions; Utilitarian Mechanism Design for Multi-Objective Optimization; Pricing Randomized Allocations; Universal ?-approximators for Integrals; Optimally Reconstructing Weighted Graphs Using Queries; Online Learning with Queries; Coresets and Sketches for High Dimensional Subspace Approximation Problems; Convergence, Stability, and Discrete Approximation of Laplace Spectra; Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities; Fast SDP Algorithms for Constraint Satisfaction Problems; Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications; Correlation Clustering with Noisy Input; A Polynomial Time Approximation Scheme for k-Consensus Clustering; Google's Auction for TV Ads; A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs; Solving the Replacement Paths Problem for Planar Directed Graphs in O (n log n) Time; Bounding Variance and Expectation of Longest Path Lengths in DAGs; Highway Dimension, Shortest Paths, and Provably Efficient Algorithms; Maximum Flows and Parametric Shortest Paths in Planar Graphs; On the Equilibria of Alternating Move Games; Monotonicity in Bargaining Networks; Sharp Dichotomies for Regret Minimization in Metric Spaces; Solving Simple Stochastic Tail Games; One-Counter Markov Decision Processes; On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture; An Improved Construction of Progression-Free Sets; Geometric Optimization and Sums of Algebraic Functions; Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface; How Far Can You Reach?; A Model of Computation for MapReduce; Synchrony and Asynchrony in Neural Networks; Distributed Agreement with Optimal Communication Complexity; How Good is the Chord Algorithm?; Deterministic Algorithms for the Lovász Local Lemma; A Deterministic Truthful PTAS for Scheduling Related Machines; A Fourier Space Algorithm for Solving Quadratic Assignment Problems; EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard; Reconstructing Approximate Phylogenetic Trees from Quartet Samples; Shape Replication through Self-Assembly and RNase Enzymes; On the Possibility of Faster SAT Algorithms; Paired Approximation Problems and Incompatible Inapproximabilities; Correlation Robust Stochastic Optimization; Approximability of Robust Network Design; Differentially Private Combinatorial Optimization; Efficiently Decodable Non-adaptive Group Testing; 1-Pass Relative-Error Lp-Sampling with Applications; On the Exact Space Complexity of Sketching and Streaming Small Norms; A Locality-Sensitive Hash for Real Vectors; Lower Bounds for Sparse Recovery; Flow-Cut Gaps for Integer and Fractional Multiflows; A Max-Flow/Min-Cut Algorithms for a Class of Wireless Networks; Testing Additive Integrality Gaps; Classified Stable Matching; Basis Reduction and the Complexity of Brand-and-Bound; Randomized Shellsort: A Simple Oblivious Sorting Algorithm; Data-Specific Analysis of String Sorting; Fast Distance Multiplication of Unit-Monge Matrices; Regular Expression Matching with Multi-Strings and Intervals; Road Network Reconstruction for Organizing Paths; The Power of Convex Relaxation: The Surprising Stories of Matrix Completion and Compressed Sensing; An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling; Resource Minimization for Fire Containment; Algorithms and Complexity for Periodic Real-Time Scheduling; Energy Efficient Scheduling via Partial ShutdownSPRT is 1.86-Competitive for Completion Time Scheduling; The Rank of Diluted Random Graphs; The Scaling Window for a Random Graph with a Given Degree Sequence; Efficient Broadcast on Random Geometric Graphs; Speeding Up Random Walks with Neighborhood Exploration; Vertices of Degree k in Random Maps; Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs; Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures; Faster Exponential Time Algorithms for the Shortest Vector Problem; Streaming Algorithms for Extent Problems in High Dimensions; Deletion Without Rebalancing in Balanced Binary Trees; On Linear and Semidefinite Programming Relaxations for Hypergraph Matching; Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph; Tree Embeddings for Two-Edge-Connected Network Design; A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover; Self-improving Algorithms for Convex Hulls; The Forest Hiding Problem; Terrain Guarding is NP-Hard; Hardness Results for Homology Localization; Orthogonal Ham-Sandwich Theorem in R3; The (1 + ?)-Choice Process and Weighted Balls-into-Bins; Quasirandom Load Balancing; Thim Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Start Shaped Bodies; Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees; Rumour Spreading and Graph Conductance