Proc. 18th annual ACM-SIAM symposium on discrete algorithms (SIAM 2007)

Hal Gabow9780898716245, 0898716241

Discrete mathematics and graph theory, including combinatorics, combinatorial optimization and networks. Preface Acknowledgments Region-Fault Tolerant Geometric Spanners, M. A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson A PTAS for TSP with Neighborhoods among Fat Regions in the Plane, Joseph S. B. Mitchell Optimal Dynamic Vertical Ray Shooting in Rectilinear Planar Subdivisions, Yoav Giyora and Haim Kaplan Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition, David Eppstein A Near Linear Time Constant Factor Approximation for Euclidean Bichromatic Matching (Cost), Piotr Indyk Compacting Cuts: A New Linear Formulation for Minimum Cut, Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, and Ojas Parekh Linear Programming Relaxations of Maxcut, Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems, Moses Charikar, Konstantin Makarychev, and Yury Makarychev Improved Bounds for the Symmetric Rendezvous Value on the Line, Qiaoming Han, Donglei Du, Juan Vera, and Luis F. Zuluaga Efficient Solutions to Relaxations of Combinatorial Problems with Submodular Penalties via the Lovász Extension and Non-smooth Convex Optimization, Fabián A. Chudak and Kiyohito Nagano Multiple Source Shortest Paths in a Genus g Graph, Sergio Cabello and Erin W. Chambers Obnoxious Centers in Graphs, Sergio Cabello and Günter Rote Maximum Matching in Graphs with an Excluded Minor, Raphael Yuster and Uri Zwick Faster Dynamic Matchings and Vertex Connectivity, Piotr Sankowski Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi Analytic Combinatorics A Calculus of Discrete Structures, Philippe Flajolet Equilibria in Online Games,Roee Engelberg and Joseph (Seffi) Naor The Approximation Complexity of Win-Lose Games, Xi Chen, Shang-Hua Teng, and Paul Valiant Convergence to Approximat

---

Table of contents :
PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS……Page 1
CONTENTS……Page 4
PREFACE……Page 14
ACKNOWLEDGMENTS……Page 15
Region-Fault Tolerant Geometric Spanners……Page 18
Compacting cuts:a new linear formulation for minimum cut……Page 60
Multiple Source Shortest Paths in a Genus g Graph……Page 106
Analytic Combinatorics A Calculus of Discrete Structures……Page 154
Equilibria in Online Games……Page 166
Better Online Buffer Management……Page 216
Minimizing Movement……Page 275
Model-driven Optimization using Adaptive Probes……Page 325
An unbiased pointing operator for unlabeled structures, with applications to counting and sampling……Page 373
Deterministic pivoting algorithms for constrained ranking and clustering problems……Page 422
An Elementary Construction of Constant-Degree Expanders……Page 471
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion……Page 519
Resilient Search Trees……Page 564
Testing for a theta……Page 612
Deterministic rendezvous, treasure hunts and strongly universal exploration sequences……Page 616
Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment……Page 662
A Network Formation Game for Bipartite Exchange Economies……Page 714
On Bregman Voronoi Diagrams……Page 763
Energy Efficient Online Deadline Scheduling……Page 812
Maximum s-t-flow with k crossings in O(k3nlog n) time……Page 860
Noisy binary search and its applications……Page 898
Semi-oblivious Routing: Lower Bounds……Page 946
All-Pairs Bottleneck Paths in Vertex Weighted Graphs……Page 995
Combinatorial Algorithms for Web Search Engines – Three Success Stories……Page 1039
k-means++: The Advantages of Careful Seeding……Page 1044
Reconstruction Using Witness Complexes……Page 1093
Games of fixed rank: A hierarchy of bimatrix games……Page 1141
The Independent Even Factor Problem……Page 1188
Quantum Algorithms for Simon’s Problem Over General Groups……Page 1234
Approximation Algorithms for Node-Weighted Buy-at-Bulk Network Design……Page 1282
AUTHOR INDEX……Page 1332