Loading... Please wait...

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms

Hover over image to zoom

Order Code:

 Product Description

Moses Charikar, Editor


2010 / xviii + 1667 / Softcover /ISBN: 978-0-898717-01-3 / List Price $211.50 / SIAM Member Price $148.05 / Order Code PR135

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.

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

Limited quantity of printed version available.



ISBN: 9780898717013

 Find Similar Products by Category

Vendors Other Products

 Product Reviews

This product hasn't received any reviews yet. Be the first to review this product!

You Recently Viewed...



Follow us on

Copyright 2017 SIAM Bookstore. All Rights Reserved.
Sitemap | BigCommerce Premium Themes by PSDCenter

Society for Industrial and Applied Mathematics 3600 Market St., 6th Fl. Philadelphia, PA 19104-2688 USA +1-215-382-9800 FAX: +1-215-386-7999 www.siam.org email: siambooks@siam.org

Click the button below to add the Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms to your wish list.