Symposium held in Miami, Florida, January 2224, 2006. This symposium is jointly sponsored by the ACM Special Interest Group on Algorithms and Computation Theory and the SIAM Activity Group on Discrete Mathematics. Preface; Acknowledgments; Session 1A: Confronting Hardness Using a Hybrid Approach, Virginia Vassilevska, Ryan Williams, and Shan Leung Maverick Woo; A New Approach to Proving Upper Bounds for MAX-2-SAT, Arist Kojevnikov and Alexander S. Kulikov, Measure and Conquer: A Simple O(20.288n) Independent Set Algorithm, Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch; A Polynomial Algorithm to Find an Independent Set of Maximum Weight in a Fork-Free Graph, Vadim V. Lozin and Martin Milanic; The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity, Wolfgang W. Bein, Mordecai J. Golin, Larry L. Larmore, and Yan Zhang; Session 1B: Local Versus Global Properties of Metric Spaces, Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala; Directed Metrics and Directed Graph Partitioning Problems, Moses Charikar, Konstantin Makarychev, and Yury Makarychev; Improved Embeddings of Graph Metrics into Random Trees, Kedar Dhamdhere, Anupam Gupta, and Harald Räcke; Small Hop-diameter Sparse Spanners for Doubling Metrics, T-H. Hubert Chan and Anupam Gupta; Metric Cotype, Manor Mendel and Assaf Naor; Session 1C: On Nash Equilibria for a Network Creation Game, Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, and Liam Roditty; Approximating Unique Games, Anupam Gupta and Kunal Talwar; Computing Sequential Equilibria for Two-Player Games, Peter Bro Miltersen and Troels Bjerre Sørensen; A Deterministic Subexponential Algorithm for Solving Parity Games, Marcin Jurdziński, Mike Paterson, and Uri Zwick; Finding Nucleolus of Flow Game, Xiaotie Deng, Qizhi Fang, and Xiaoxun Sun, Session 2: Invited Plenary Abstract: Predicting the Unpredictable, Rakesh V. Vohra, Northwestern University; Session 3A: A Near-Tight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem, Sven Koenig, Apurva Mudgal, and Craig Tovey; An Asymptotic Approximation Algorithm for 3D-Strip Packing, Klaus Jansen and Roberto Solis-Oba; Facility Location with Hierarchical Facility Costs, Zoya Svitkina and Éva Tardos; Combination Can Be Hard: Approximability of the Unique Coverage Problem, Erik D. Demaine, Uriel Feige, Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour; Computing Steiner Minimum Trees in Hamming Metric, Ernst Althaus and Rouven Naujoks; Session 3B: Robust Shape Fitting via Peeling and Grating Coresets, Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu; Tightening Non-Simple Paths and Cycles on Surfaces, Éric Colin de Verdière and Jeff Erickson; Anisotropic Surface Meshing, Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Rephael Wenger; Simultaneous Diagonal Flips in Plane Triangulations, Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, and David R. Wood; Morphing Orthogonal Planar Graph Drawings, Anna Lubiw, Mark Petrick, and Michael Spriggs; Session 3C: Overhang, Mike Paterson and Uri Zwick; On the Capacity of Information Networks, Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert Kleinberg, and April Rasala Lehman; Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding, Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, and Mihai Pătraşcu; Self-Improving Algorithms, Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu; Cake Cutting Really is Not a Piece of Cake, Jeff Edmonds and Kirk Pruhs; Session 4A: Testing Triangle-Freeness in General Graphs, Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron; Constraint Solving via Fractional Edge Covers, Martin Grohe and Dániel Marx; Testing Graph Isomorphism, Eldar Fischer and Arie Matsliah; Efficient Construction of Unit Circular-Arc Models, Min Chih Lin and Jayme L. Szwarcfiter, On The Chromatic Number of Some Geometric Hypergraphs, Sh
Author(s): the ACM Special Interest Group
Series: Proceedings in Applied Mathematics
Edition: SIAM
Publisher: SIAM, Society for Industrial and Applied Mathematics
Year: 2006
Language: English
Pages: 1261
PROCEEDINGS OF THE SEVENTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS......Page 1
CONTENTS......Page 4
PREFACE......Page 14
ACKNOWLEDGMENTS......Page 15
Confronting Hardness Using a Hybrid Approach*......Page 20
A New Approach to Proving Upper Bounds for MAX-2-SAT......Page 30
Measure and Conquer:A Simple O(2? 288/?) Independent Set Algorithm......Page 37
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph......Page 45
The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity......Page 50
Local versus Global Properties of Metric Spaces Extended abstract......Page 60
Directed Metrics and Directed Graph Partitioning Problems......Page 70
Improved Embeddings of Graph Metrics into Random Trees*......Page 80
Small Hop-diameter Sparse Spanners for Doubling Metrics5......Page 89
Metric Cotype*......Page 98
On Nash Equilibria for a Network Creation Game......Page 108
approximating Unique Games......Page 118
Computing sequential equilibria for two-player games......Page 126
A deterministic subexponential algorithm for solving parity games......Page 136
Finding Nucleolus of Flow Game*......Page 143
SESSION 2: INVITED PLENARY ABSTRACT......Page 151
a Neaer-Tighht Approximation Lower Bound and Algorithm for the Kidnapped......Page 152
An Asymptotic Approximation Algorithm for SD-Strip Packing......Page 162
Facility Location with Hierarchical Facility Costs......Page 172
Combination Can Be Hard:Approximability of the Unique Coverage Problem......Page 181
Computing Steiner Minimum Trees in Hamming Metric......Page 191
Robust Shape Fitting via Peeling and Grating Coresets:......Page 201
Tightening Non-Simple Paths and Cycles on Surfaces*......Page 211
Anisotropic Surface Meshing......Page 221
Simultaneous Diagonal Flips in Plane Triangulations*......Page 231
Morphing Orthogonal Planar Graph Drawings*......Page 241
Overhang......Page 250
On the Capacity of Information Networks......Page 260
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding......Page 270
Self- Improving Algorithms *......Page 280
Cake Cutting Really is Not a Piece of Cake......Page 290
Testing Triangle-Freeness in General Graphs......Page 298
Constraint Solving via Fractional Edge Covers......Page 308
Testing graph isomorphism......Page 318
Efficient Construction of Unit Circular-Arc Models......Page 328
On The Chromatic Number of Some Geometric Hypergraphs......Page 335
A Robust Maximum Completion Time Measure for Scheduling......Page 343
Extra Unit-Speed Machines are Almost as Powerful as......Page 353
Improved approximation algorithms for Broadcast Scheduling......Page 363
Distributed Selfish Load Balancing"......Page 373
Scheduling Unit Tasks to Minimize the Number of Idle Periods:A Polynomial Time Algorithm for Offline Dynamic Power Management......Page 383
Rank/Select Operations on Large Alphabets: a Tool for Text......Page 387
O(loglogn)-Competitive Dynamic Binary Search Trees*......Page 393
The Rainbow Skip Graph:A Fault-Tolerant Constant-Degree Distributed Data Structure......Page 403
Design of Data Structures for Mergeable Trees*......Page 413
Implicit Dictionaries with O(l) Modifications per Update and Fast Search......Page 423
Sampling Binary Contingency Tables with a Greedy Start......Page 433
Asymmetric Balanced Allocation with Simple Hash Functions'......Page 443
Balanced Allocation on Graphs......Page 453
Superiority and Complexity of the Spaced Seeds......Page 463
Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time......Page 473
Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem......Page 483
Finding Large Sticks and Potatoes in Polygons......Page 493
Randomized Incremental Constructions of Three-Dimensional Convex Hulls and Planar Voronoi Diagrams, and Approximate Range Counting*......Page 503
Vertical Ray Shooting and Computing Depth Orders for Fat Objects......Page 513
On the Number of Plane Graphs......Page 523
All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mri) Time......Page 533
An O(nlogn) algorithm for maximum si-flow in a directed planar......Page 543
A simple GAP-canceling algorithm for the generalized maximum flow problem......Page 553
Four Point Conditions and Exponential Neighborhoods for Symmetric TSP......Page 563
Upper Degree-Constrained Partial Orientations......Page 573
On the tandem duplication-random loss model of genome rearrangement......Page 583
Reducing Tile Complexity for Self-Assembly Through Temperature Programming......Page 590
Cache-Oblivious String Dictionaries......Page 600
Cache-Oblivious Dynamic Programming *......Page 610
A Computational Study of External-Memory BFS Algorithms^......Page 620
Tight Approximation Algorithms for Maximum General Assignment......Page 630
Approximating the fc-Multicut Problem......Page 640
The Prize-Collecting Generalized Steiner Tree Problem Via A New Approach Of Primal-Dual Schema......Page 650
8/7-Approximation Algorithm for (1,2)-TSP......Page 660
Improved Lower and Upper Bounds......Page 668
Leontief Economies Encode Nonzero Sum Two-Player Games......Page 678
Bottleneck Links, Variable Demand,and the Tragedy of the Commons......Page 687
The Complexity of Quantitative Concurrent Parity Games *......Page 697
Equilibria for Economies with Production: Constant-Returns Technologies......Page 707
Approximation Algorithms for Wavelet Transform Coding of Data......Page 717
Simpler algorithm for estimating frequency moments of data streams......Page 727
Trading Off Space for Passes in Graph Streaming Problems......Page 733
Maintaining Significant Stream Statistics over Sliding Windows......Page 743
Streaming and Sublinear Approximation of Entropy and Information Distances......Page 752
FPTAS for mixed-integer polynomial optimization......Page 762
Linear Programming and Unique Sink Orientations......Page 768
Generating all vertices of a polyhedron is hard*......Page 777
A Semidefinite Programming Approach to Tensegrity Theory and......Page 785
Ordering by weighted number of wins gives a good ranking for......Page 795
Weighted Isotonic Regression under the LI Norm......Page 802
Oblivious String Embeddings and Edit Distance Approximations......Page 811
Spanners and emulators with sublinear distance errors......Page 821
Certifying Large Branch-width......Page 829
DAG-width - Connectivity Measure for Directed Graphs......Page 833
On the diameter of Eulerian orientations of graphs......Page 841
Max-Tolerance Graphs as Intersection Graphs:Cliques, Cycles, and Recognition *......Page 851
Subgraph characterization of Red/Blue-Split Graph and Konig Egervary Graphs......Page 861
Critical chromatic number and the complexity of perfect packings in graphs......Page 870
On the Number of Crossing-Free Matchings,(Cycles, and Partitions)*......Page 879
Slow Mixing of Glauber Dynamics Via Topological Obstructions......Page 889
Quantum Verification of Matrix Products......Page 899
Counting without sampling. New algorithms for enumeration problems using......Page 909
New Lower Bounds for Oblivious Routing in Undirected Graphs......Page 937
Anytime Algorithms for Multi-Armed Bandit Problems......Page 947
Robbing the bandit: Less regret in online geometric optimization against an......Page 956
On the Competitive Ratio of Evaluating Priced Functions......Page 963
Randomized Online Algorithms for Minimum Metric Bipartite Matching......Page 973
SESSION 10: INVITED PLENARY ABSTRACT......Page 979
Analyzing BitTorrent and Related Peer-to-Peer Networks......Page 980
Oblivious Network Design......Page 989
The Price of Being Near-Sighted......Page 999
Scalable Leader Election......Page 1009
Deterministic boundary recognition and topology extraction......Page 1019
Improved lower bounds for embeddings into LI......Page 1029
i Spreading Metrics For Vertex Ordering Problems......Page 1037
Trees and Markov convexity......Page 1047
An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing......Page 1057
A Tight Upper Bound on the Probabilistic Embedding of Series-Parallel Graphs......Page 1064
Single-Value Combinatorial Auctions and Implementation in......Page 1073
An Improved Approximation Algorithm for Combinatorial Auctions......Page 1083
Revenue Maximization When Bidders Have Budgets......Page 1093
Knapsack Auctions......Page 1102
Single-Minded Unlimited Supply Pricing on Sparse Instances......Page 1112
The Complexity of Matrix Completion......Page 1122
Relating singular values and discrepancy of weighted directed graphs......Page 1131
Matrix Approximation and Projective Clustering via Volume Sampling"......Page 1136
Sampling Algorithms for ^2 Regression and Applications......Page 1146
The Hunting of the Bump: On Maximizing Statistical Discrepancy......Page 1156
A general approach for incremental approximation and hierarchical clustering......Page 1166
The Space Complexity of Pass-Efficient Algorithms for Clustering......Page 1176
Correlation Clustering with a Fixed Number of Clusters......Page 1186
On fc-Median Clustering in High Dimensions......Page 1196
Entropy based Nearest Neighbor Search in High Dimensions......Page 1205
A Dynamic Data Structure for 3-d Convex Hulls and......Page 1215
Efficient Algorithms for Substring Near Neighbor Problem......Page 1222
Many distances in planar graphs5......Page 1232
Pattern Matching with Address Errors: Rearrangement Distances......Page 1240
Squeezing Succinct Data Structures into Entropy Bounds......Page 1249
AUTHOR INDEX......Page 1259
