Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Proceedings in Applied Mathematics)

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