2006 / xviii + 1242 pages / Softcover / ISBN: 978-0-898716-05-4 / List Price $156.50 / SIAM Member Price $109.55 / Order Code PR122
Symposium held in Miami, Florida, January 22-24, 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.
Contents
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, Shakhar Smorodinsky; Session 4B: A Robust Maximum Completion Time Measure for Scheduling, Moses Charikar and Samir Khuller; Extra Unit-Speed Machines are Almost as Powerful as Speedy Machines for Competitive Flow Time Scheduling, Ho-Leung Chan, Tak-Wah Lam, and Kin-Shing Liu; Improved Approximation Algorithms for Broadcast Scheduling, Nikhil Bansal, Don Coppersmith, and Maxim Sviridenko; Distributed Selfish Load Balancing, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, Zengjian Hu, and Russell Martin; Scheduling Unit Tasks to Minimize the Number of Idle Periods: A Polynomial Time Algorithm for Offline Dynamic Power Management, Philippe Baptiste; Session 4C: Rank/Select Operations on Large Alphabets: A Tool for Text Indexing, Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao; O(log log n)-Competitive Dynamic Binary Search Trees, Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator; The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure, Michael T. Goodrich, Michael J. Nelson, and Jonathan Z. Sun; Design of Data Structures for Mergeable Trees, Loukas Georgiadis, Robert E. Tarjan, and Renato F. Werneck; Implicit Dictionaries with O(1) Modifications per Update and Fast Search, Gianni Franceschini and J. Ian Munro; Session 5A: Sampling Binary Contingency Tables with a Greedy Start, Ivona Bezáková, Nayantara Bhatnagar, and Eric Vigoda; Asymmetric Balanced Allocation with Simple Hash Functions, Philipp Woelfel; Balanced Allocation on Graphs, Krishnaram Kenthapadi and Rina Panigrahy; Superiority and Complexity of the Spaced Seeds, Ming Li, Bin Ma, and Louxin Zhang; Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time, Michael Krivelevich and Dan Vilenchik; Session 5B: Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem, Jie Gao, Michael Langberg, and Leonard J. Schulman; Finding Large Sticks and Potatoes in Polygons, Olaf Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, and Arik Sityon; Randomized Incremental Construction of Three-Dimensional Convex Hulls and Planar Voronoi Diagrams, and Approximate Range Counting, Haim Kaplan and Micha Sharir; Vertical Ray Shooting and Computing Depth Orders for Fat Objects, Mark de Berg and Chris Gray; On the Number of Plane Graphs, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferran Hurtado, and Hannes Krasser; Session 5C: All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time, Timothy M. Chan; An O(n log n) Algorithm for Maximum st-Flow in a Directed Planar Graph, Glencora Borradaile and Philip Klein; A Simple GAP-Canceling Algorithm for the Generalized Maximum Flow Problem, Mateo Restrepo and David P. Williamson; Four Point Conditions and Exponential Neighborhoods for Symmetric TSP, Vladimir Deineko, Bettina Klinz, and Gerhard J. Woeginger; Upper Degree-Constrained Partial Orientations, Harold N. Gabow; Session 7A: On the Tandem Duplication-Random Loss Model of Genome Rearrangement, Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, and Satish Rao; Reducing Tile Complexity for Self-Assembly Through Temperature Programming, Ming-Yang Kao and Robert Schweller; Cache-Oblivious String Dictionaries, Gerth Stølting Brodal and Rolf Fagerberg; Cache-Oblivious Dynamic Programming, Rezaul Alam Chowdhury and Vijaya Ramachandran; A Computational Study of External-Memory BFS Algorithms, Deepak Ajwani, Roman Dementiev, and Ulrich Meyer; Session 7B: Tight Approximation Algorithms for Maximum General Assignment Problems, Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko; Approximating the k-Multicut Problem, Daniel Golovin, Viswanath Nagarajan, and Mohit Singh; The Prize-Collecting Generalized Steiner Tree Problem Via A New Approach Of Primal-Dual Schema, Mohammad Taghi Hajiaghayi and Kamal Jain; 8/7-Approximation Algorithm for (1,2)-TSP, Piotr Berman and Marek Karpinski; Improved Lower and Upper Bounds for Universal TSP in Planar Metrics, Mohammad T. Hajiaghayi, Robert Kleinberg, and Tom Leighton; Session 7C: Leontief Economies Encode NonZero Sum Two-Player Games, B. Codenotti, A. Saberi, K. Varadarajan, and Y. Ye; Bottleneck Links, Variable Demand, and the Tragedy of the Commons, Richard Cole, Yevgeniy Dodis, and Tim Roughgarden; The Complexity of Quantitative Concurrent Parity Games, Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger; Equilibria for Economies with Production: Constant-Returns Technologies and Production Planning Constraints, Kamal Jain and Kasturi Varadarajan; Session 8A: Approximation Algorithms for Wavelet Transform Coding of Data Streams, Sudipto Guha and Boulos Harb; Simpler Algorithm for Estimating Frequency Moments of Data Streams, Lakshimath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha; Trading Off Space for Passes in Graph Streaming Problems, Camil Demetrescu, Irene Finocchi, and Andrea Ribichini; Maintaining Significant Stream Statistics over Sliding Windows, L.K. Lee and H.F. Ting; Streaming and Sublinear Approximation of Entropy and Information Distances, Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian; Session 8B: FPTAS for Mixed-Integer Polynomial Optimization with a Fixed Number of Variables, J. A. De Loera, R. Hemmecke, M. Köppe, and R. Weismantel; Linear Programming and Unique Sink Orientations, Bernd Gärtner and Ingo Schurr; Generating All Vertices of a Polyhedron is Hard, Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich; A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs, Anthony Man-Cho So and Yinyu Ye; Ordering by Weighted Number of Wins Gives a Good Ranking for Weighted Tournaments, Don Coppersmith, Lisa Fleischer, and Atri Rudra; Session 8C: Weighted Isotonic Regression under L1 Norm, Stanislav Angelov, Boulos Harb, Sampath Kannan, and Li-San Wang; Oblivious String Embeddings and Edit Distance Approximations, Tuğkan Batu, Funda Ergun, and Cenk Sahinalp; Spanners and Emulators with Sublinear Distance Errors, Mikkel Thorup and Uri Zwick; Certifying Large Branch-Width, Sang-il Oum and Paul Seymour; DAG-width—Connectivity Measure for Directed Graphs, Jan Obdrzálek; Session 9A: On the Diameter of Eulerian Orientations of Graphs, Laszlo Babai; Max-Tolerance Graphs as Intersecton Graphs: Cliques, Cycles, and Recognition, Michael Kaufmann, Jan Kratochvil, Katharina A. Lehmann, and Amarendran R. Subramanian; Subgraph Characterization of Red/Blue-Split Graphs and Kőnig Egerváry Graphs, Ephraim Korach, Thành Nguyen, and Britta Pies; Critical Chromatic Number and the Complexity of Perfect Packings in Graphs, Daniela Kühn and Deryk Osthus; On the Number of Crossing-Free Matchings, (Cycles, and Partitions), Micha Sharir and Emo Welzl; Session 9B: Slow Mixing of Glauber Dynamics via Topological Obstructions, Dana Randall; Quantum Verification of Matrix Products, Harry Buhrman and Robert Spalek; Counting Without Sampling. New Algorithms for Enumeration Problems Using Statistical Physics, Antar Bandyopadhyay and David Gamarnik; Accelerating Simulated Annealing for Combinatorial Counting Problems, Ivona Bezáková, Daniel Stefankovič, Vijay V. Vazirani, and Eric Vigoda; Query-Efficient Algorithms for Polynomial Interpoltion over Composites, Parikshit Gopalan; Session 9C: New Lower Bounds for Oblivious Routing in Undirected Graphs, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, and Harald Räcke; Anytime Algorithms for Multi-Armed Bandit Problems, Robert Kleinberg; Robbing the Bandit: Less Regret in Online Geometric Optimization Against an Adaptive Adversary, Varsha Dani and Thomas P. Hayes; On the Competitive Ratio of Evaluating Priced Functions, Ferdinando Cicalese and Eduardo Sany Laber; Randomized Online Algorithms for Minimum Metric Bipartite Matching, Adam Meyerson, Akash Nanavati, and Laura Poplawski; Session 10: Invited Plenary Abstract: Random Graphs, Alan Frieze, Carnegie Mellon University; Session 11A: Analyzing BitTorrent and Related Peer-to-Peer Networks, David Arthur and Rina Panigraphy; Oblivious Network Design, Anupam Gupta, Mohammad T. Hajiaghayi, and Harald Räcke; The Price of Being Near-Sighted, Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer; Scalable Leader Election, Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee; Deterministic Boundary Recognition and Topology Extraction for Large Sensor Networks, A. Kröller, Sandor P. Fekete, Dennis Pfisterer, and Stefan Fischer; Session 11B: Improved Lower Bounds for Embeddings into L1 , Robert Krautghamer and Yuval Rabani; l_2^2 Spreading Metrics for Vertex Ordering Problems, Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, and Satish Rao; Trees, Markov convexity, James R. Lee, Assaf Naor, and Yuval Peres; An Algorithmic Friedman-Pippenger Theorem on Tree Embeddings and Applications to Routing, D. Dellamonica, Jr. and Y. Kohayakawa; A Tight Upper Bound on the Probabilistic Embedding of Series-Parallel Graphs, Yuval Emek and David Peleg; Session 11C: Single-Value Combinatorial Auctions and Implementation in Undominated Strategies, Moshe Babaioff, Ron Lavi, and Elan Pavlov; An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders, Shahar Dobzinski and Michael Schapira; Revenue Maximization When Bidders Have Budgets, Zoë Abrams; Knapsack Auctions, Gagan Aggarwal and Jason Hartline; Single-Minded Unlimited Supply Pricing on Sparse Instances, Patrick Briest and Piotr Krysta; Session 12A: The Complexity of Matrix Completion, Nicholas J. A. Harvey, David R. Karger, and Sergey Yekhanin; Relating Singular Values and Discrepancy of Weighted Directed Graphs, Steven Butler; Matrix Approximation and Projective Clustering via Volume Sampling, Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang; Sampling Algorithms for l2 Regression and Applications, Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan; The Hunting of the Bump: On Maximizing Statistical Discrepancy, Deepak Agarwal, Jeff M. Phillips, and Suresh Venkatasubramanian; Session 12 B: A General Approach for Incremental Approximation and Hierarchical Clustering, Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson; The Space Complexity of Pass-Efficient Algorithms for Clustering, Kevin L. Chang and Ravi Kannan; Correlation Clustering with a Fixed Number of Clusters, Ioannis Giotis and Venkatesan Guruswami; On k-Median Clustering in High Dimensions, Ke Chen; Entropy Based Nearest Neighbor Search in High Dimensions, Rina Panigrahy; Session 12C: A Dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries, Timothy M. Chan; Efficient Algorithms for Substring Near Neighbor Problem, Alexandr Andoni and Piotr Indyk; Many Distances in Planar Graphs, Sergio Cabello; Pattern Matching with Address Errors: Rearrangement Distances, Amihood Amir, Yonatan Aumann, Gary Benson, Avivit Levy, Ohad Lipsky, Ely Porat, Steven Skiena, and Uzi Vishne; Squeezing Succinct Data Structures into Entropy Bounds, Kunihiko Sadakane and Roberto Grossi; Author Index.
ISBN: 9780898716054