Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Proceedings Of The Eighteenth Annual Acm Siam Symposium On Discrete Algorithms


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 Approximate Nash Equilibria in Congestion Games, Steve Chien and Alistair Sinclair Efficient Contention Resolution Protocols for Selfish Agents, Amos Fiat, Yishay Mansour, and Uri Nadav Strong Price of Anarchy,Nir Andelman, Michal Feldman, and Yishay Mansour Better Online Buffer Management , Fei Li, Jay Sethuraman, and Clifford Stein Considering Suppressed Packets Improves Buffer Management in QoS Switches, Matthias Englert and Matthias Westermann Instability of FIFO in the Permanent Sessions Model at Arbitrarily Small Network Loads, Matthew Andrews On the Separation and Equivalence of Paging Strategies,Spyros Angelopoulos, Reza Dorrigiv, and Alejandro L pez-Ortiz Pull-Based Data Broadcast with Dependencies: Be Fair to Users, Not to Items,Julien Robert and Nicolas Schabanel Improved Bounds for the Online Steiner Tree Problem in Graphs of Bounded Edge-Asymmetry, Spyros Angelopoulos Minimizing Movement, Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam Optimization Problems in Multiple-Interval Graphs, Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz Approximation Algorithms via Contraction Decomposition, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar A 1.875 Approximation Algorithm for the Stable Marriage Problem, Kazuo Iwama, Shuichi Miyazaki, and Naoya Yamauchi Improved Algorithms for Path, Matching, and Packing Problems, Jianer Chen, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang Model-Driven Optimization Using Adaptive Probes, Sudipto Guha and Kamesh Munagala Estimating the Sortedness of a Data Stream, Parikshit Gopalan, T.S. Jayram, Robert Krauthgamer, and Ravi Kumar A Near-Optimal Algorithm for Computing the Entropy of a Stream, Amit Chakrabarti, Graham Cormode, and Andrew McGregor The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences, Xiaoming Sun and David P. Woodruff Efficient Aggregation Algorithms for Probabilistic Data, T.S. Jayram, Satyen Kale, and Erik Vee An Unbiased Pointing Operator for Unlabeled Structures, with Applications to Counting and Sampling, Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan Vigerske Approximating Entropy from Sublinear Samples, Mickey Brautbar and Alex Samorodnitsky Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus, David Galvin and Dana Randall Probabilistic Analysis of Linear Programming Decoding, Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, and Martin J. Wainwright Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes, Adam Smith Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems, Anke van Zuylen, Rajneesh Hegde, Kamal Jain, and David P. Williamson Aggregation of Partial Rankings, p-Ratings and Top-m Lists, Nir Ailon Algorithms and Incentives for Robust Ranking, Rajat Bhattacharjee and Ashish Goel Matroids, Secretary Problems, and Online Mechanisms, Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg An Algebraic Algorithm for Weighted Linear Matroid Intersection, Nicholas J. A. Harvey An Elementary Construction of Constant-Degree Expanders, Noga Alon, Oded Schwartz, and Asaf Shapira The k-Orientability Thresholds for G_{n,p}, Daniel Fernholz and Vijaya Ramachandran The Random Graph Threshold for k-Orientiability and a Fast Algorithm for Optimal Multiple-Choice Allocation, Julie Anne Cain, Peter Sanders, and Nick Wormald On Extremal Subgraphs of Random Graphs, Graham Brightwell, Konstantinos Panagiotou, and Angelika Steger Online Vertex Colorings of Random Graphs without Monochromatic Subgraphs, Martin Marciniszyn and Reto Sp hel On Testable Properties in Bounded Degree Graphs, Artur Czumaj and Christian Sohler Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion, Ittai Abraham, Yair Bartal, and Ofer Neiman Approximation Algorithms for Embedding General Metrics into Trees, Mihai Badoiu, Piotr Indyk, and Anastasios Sidiropoulos Embedding into $l^2_{infty}$ Is Easy, Embedding into $l^3_{infty}$ Is NP-Complete, Jeff Edmonds Efficient Subspace Approximation Algorithms, Nariankadu D. Shyamalkumar and Kasturi Varadarajan A Divide and Conquer Algorithm for d-Dimensional Arrangement, Moses Charikar, Konstantin Makarychev, and Yury Makarychev Resilient Search Trees, Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano Randomization Does Not Help Searching Predecessors, Mihai Patrascu and Mikkel Thorup Dynamic Weighted Ancestors, Tsvi Kopelowitz and Moshe Lewenstein Ultra-succinct Representation of Ordered Trees, Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung Tree Exploration with Logarithmic Memory, Leszek Gasieniec, Andrzej Pelc, Tomasz Radzik, and Xiaohui Zhang Testing for a Theta, Maria Chudnovsky and Paul Seymour Deterministic Rendezvous, Treasure Hunts and Strongly Universal Exploration Sequences, Amnon Ta-Shma and Uri Zwick Planar Graphs Are in 1-STRING, J. Chalopin, D. Gon alves, and P. Ochem On the Bandwidth Conjecture for 3-Colourable Graphs, Julia B ttcher, Mathias Schacht, and Anusch Taraz Sandpile Transience on the Grid is Polynomially Bounded, L'szl Babai and Igor Gorodezky Digraph Measures: Kelly Decompositions, Games, and Orderings, Paul Hunter and Stephan Kreutzer Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment, C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, and Louxin Zhang Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree, Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang Whole Genome Duplications, Multi-break Rearrangements, and Genome Halving Problem, Max A. Alekseyev and Pavel A. Pevzner Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees, J r my Barbay, Meng He, J. Ian Munro, and S. Srinivasa Rao A Simple Storage Scheme for Strings Achieving Entropy Bounds, Paolo Ferragina and Rossano Venturini A Network Formation Game for Bipartite Exchange Economies, Eyal Even-Dar, Michael Kerans, and Siddharth Suri Cheap Labor Can Be Expensive, Ning Chen and Anna R. Karlin Buying Cheap Is Expensive: Hardness of Non-parametric Multi-product Pricing, Patrick Briest and Piotr Krysta Dynamic Pricing for Impatient Bidders, Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, and Maxim Sviridenko Designing and Learning Optimal Finite Support Auctions, Edith Elkind On Bregman Voronoi Diagrams, Frank Nielsen, Jean-Daniel Boissonnat, and Richard Nock Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge, Tetsuo Asano, Jir Matou ek, and Takeshi Tokuyama Approximate Shortest Paths in Anisotropic Regions, Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang On Bounded Leg Shortest Paths Problems, Liam Roditty and Michael Segal Counting Colors in Boxes, Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin Energy Efficient Online Deadline Scheduling, Ho-Leung Chan, Wun-Tat Chan, Tak-Wah Lam, Lap-Kei Lee, Kin-Sum Mak, and Prudence W. H. Wong Speed Scaling for Weighted Flow Time, Nikhil Bansal, Kirk Pruhs, and Cliff Stein Path-Independent Load Balancing with Unreliable Machines, James Aspnes, Yang Richard Yang, and Yitong Yin Layered Multicast Scheduling for the L_infinity Objective, Qingbo Cai and Vincenzo Liberatore Lower Bounds on Average-Case Delay for Video-on-Demand Broadcast Protocols, Wei-Lung Dustin Tseng and David Kirkpatrick Maximum s-t-Flow with k Crossings in $O(k^3 n log n)$ Time, Jan M. Hochstein and Karsten Weihe Matrix Scaling by Network Flow, G nter Rote and Martin Zachariasen Single Source Multiroute Flows and Cuts on Uniform Capacity Networks, Henning Bruhn, Jakub Cern , Alexander Hall, and Petr Kolman Island Hopping and Path Colouring with Applications to WDM Network Design, Andrew McGregor and Bruce Shepherd Maximum Independent Sets in Graphs of Low Degree,



  • Condition: --
    HPB condition ratings
    • New: Item is brand new, unused and unmarked, in flawless condition.
    • Fine/Like New (F): No defects, little usage. May show remainder marks. Older books may show minor flaws.
    • Very Good (VG): Shows some signs of wear and is no longer fresh. Attractive. Used textbooks do not come with supplemental materials.
    • Good (G): Average used book with all pages present. Possible loose bindings, highlighting, cocked spine or torn dust jackets. Used textbooks do not come with supplemental materials.
    • Fair (FR): Obviously well-worn, but no text pages missing. May be without endpapers or title page. Markings do not interfere with readability. Used textbooks do not come with supplemental materials.
    • Poor (P): All text is legible but may be soiled and have binding defects. Reading copies and binding copies fall into this category. Used textbooks do not come with supplemental materials.
    Conditions Guide
  • Format: Paperback
  • Sold by: --
  • Language: English
  • Publisher: Society for Industrial & Applied
  • ISBN-13: 9780898716245
  • ISBN: 0898716241
  • Publication Year: 2007
Loading...
Loading marketplace...
HPB condition ratings
  • New: Item is brand new, unused and unmarked, in flawless condition.
  • Fine/Like New (F): No defects, little usage. May show remainder marks. Older books may show minor flaws.
  • Very Good (VG): Shows some signs of wear and is no longer fresh. Attractive. Used textbooks do not come with supplemental materials.
  • Good (G): Average used book with all pages present. Possible loose bindings, highlighting, cocked spine or torn dust jackets. Used textbooks do not come with supplemental materials.
  • Fair (FR): Obviously well-worn, but no text pages missing. May be without endpapers or title page. Markings do not interfere with readability. Used textbooks do not come with supplemental materials.
  • Poor (P): All text is legible but may be soiled and have binding defects. Reading copies and binding copies fall into this category. Used textbooks do not come with supplemental materials.
Conditions Guide
HPB condition ratings
  • New: Mint condition or still sealed (SS). Absolutely perfect in every way. New.
  • Fine/Like New (EX): No defects, little sign of use, well cared for. Plays perfectly. Close to new. Not necessarily sealed or unused, but close. Could be an unopened promotional or cut item. Sometimes called: mint-minus.
  • Very Good (VG): Will show some signs that it was played and otherwise handled by a previous owner who took good care of it.
  • Good (G): Attractive and well cared for, but no longer fresh. Minor signs of wear, scuffing or scratching, but will play almost perfectly. For vinyl: barely detectable crackles or pops.
  • Fair (FR): This item is in okay condition. For vinyl: good is not so good and the record may have low level crackles or pops when playing. CD: one or more tracks may skip.
  • Poor (P): Obviously well-worn and handled. Most vinyl collectors will not buy good or below, but some tracks on CD or vinyl will play.
Conditions Guide
HPB condition ratings
  • New: This movie is unopened and brand new.
  • Fine/Like New (EX): Near new. No defects, little sign of use. Plays perfectly. Not necessarily sealed or unused, but close. No skipping; no fuzzy or snowy frames in VHS.
  • Very Good (VG): Attractive and well cared for but no longer fresh. Minor signs of wear, but will play almost perfectly. For VHS: barely detectable distortion or very few fuzzy or snowy frames.
  • Good (G): This item is in okay condition and basically works well. There may be some minor distortion on VHS tape; slight scratching or wear on DVD.
  • Fair (FR): Basically plays, but may be obviously well-worn with some scratching or tape distortion.
  • Poor (P): Disc or tape is intact, but may be scratched or stretched. There may be skips or distortion or product defects.
Conditions Guide
×