
2010 / xviii + 1667 / Softcover /ISBN: 9780898717013 / List Price $211.50 / SIAM Member Price $148.05 / Order Code PR135
The papers in this volume were presented at the TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, held January 1719, 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.43Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model; Towards the Randomized kServer Conjecture: A PrimalDual Approach; Testing Monotone Continuous Distributions on Highdimensional Real Cubes; Property Testing and Parameter Testing for Permutations; NearOptimal Sublinear Time Algorithms for Ulam Distance; Lower Bounds for Testing Trianglefreeness in Boolean Functions; Counting Stars and Other Small Subgraphs in Sublinear Time; CellProbe Lower Bounds for Succinct Partial Sums; On the Cell Probe Complexity of Dynamic Membership; FullyFunctional 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 PoincarType Inequalities; Genus and the Geometry of the Cut Graph; Testing Planarity of Partially Embedded Graphs; Inapproximability for Planar Embedding Problems; Towards a Calculus for NonLinear 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 Mincost Network Flow: Convergence & Correctness; Finding the Jaccard Median; The Focus of Attention Problem; Recognizing a Totally Odd K4subdivision, Parity 2disjoint Rooted Paths and a Parity Cycle Through Specified Elements; Decomposition, Approximation, and Coloring of OddMinorFree Graphs; The Edge Disjoint Paths Problem with Eulerian Graphs and 4edgeconnected Graphs; On Bramble, GridLike Minors, and Parameterized Intractability of Monadic SecondOrder 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 Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing; Region Growing for MultiRoute Cuts; Asymmetric Traveling Salesman Path and Directed Latency Problems; Improved Approximation Algorithms for the Minimum Latency Problem via PrizeCollecting Strolls; Quantum Algorithms for Highly NonLinear Boolean Functions; Compact Ancestry Labeling Schemes for XML Trees; Generating a ddimensional Linear Subspace Efficiently; Algorithms for Ray Class Groups and Hilbert Class Fields; A SpaceTime Tradeoff for Permutation Problems; Algorithmic Lower Bounds for Problems Parameterized with CliqueWidth; Bidimensionality and Kernels; Solving MAXrSAT Above a Tight Lower Bound; Inapproximability for BCGBased Combinatorial Auctions; Price of Anarchy for Greedy Auctions; Incentive Compatible Budget Elicitation in Multiunit Auctions; Utilitarian Mechanism Design for MultiObjective 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 kConsensus 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; OneCounter Markov Decision Processes; On Nonlinear Forbidden 01 Matrices: A Refutation of a FrediHajnal Conjecture; An Improved Construction of ProgressionFree 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 Lovsz Local Lemma; A Deterministic Truthful PTAS for Scheduling Related Machines; A Fourier Space Algorithm for Solving Quadratic Assignment Problems; EDFschedulability of Synchronous Periodic Task Systems is coNPhard; Reconstructing Approximate Phylogenetic Trees from Quartet Samples; Shape Replication through SelfAssembly 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 Nonadaptive Group Testing; 1Pass RelativeError LpSampling with Applications; On the Exact Space Complexity of Sketching and Streaming Small Norms; A LocalitySensitive Hash for Real Vectors; Lower Bounds for Sparse Recovery; FlowCut Gaps for Integer and Fractional Multiflows; A MaxFlow/MinCut Algorithms for a Class of Wireless Networks; Testing Additive Integrality Gaps; Classified Stable Matching; Basis Reduction and the Complexity of BrandandBound; Randomized Shellsort: A Simple Oblivious Sorting Algorithm; DataSpecific Analysis of String Sorting; Fast Distance Multiplication of UnitMonge Matrices; Regular Expression Matching with MultiStrings 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 RealTime Scheduling; Energy Efficient Scheduling via Partial ShutdownSPRT is 1.86Competitive 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; CacheOblivious Dynamic Dictionaries with Update/Query Tradeoffs; Applications of Forbidden 01 Matrices to Search Tree and Path CompressionBased 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 TwoEdgeConnected Network Design; A Constant Factor Approximation Algorithm for Generalized MinSum Set Cover; Selfimproving Algorithms for Convex Hulls; The Forest Hiding Problem; Terrain Guarding is NPHard; Hardness Results for Homology Localization; Orthogonal HamSandwich Theorem in R3; The (1 + β)Choice Process and Weighted BallsintoBins; 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