Proceedings in Applied Mathematics 122
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 MAX2SAT, 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 ForkFree Graph, Vadim V. Lozin and Martin Milanic; The KnuthYao QuadrangleInequality Speedup is a Consequence of TotalMonotonicity, 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 Hopdiameter Sparse Spanners for Doubling Metrics, TH. 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 EvenDar, Yishay Mansour, and Liam Roditty; Approximating Unique Games, Anupam Gupta and Kunal Talwar; Computing Sequential Equilibria for TwoPlayer 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 NearTight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem, Sven Koenig, Apurva Mudgal, and Craig Tovey; An Asymptotic Approximation Algorithm for 3DStrip Packing, Klaus Jansen and Roberto SolisOba; 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 HarPeled, and Hai Yu; Tightening NonSimple Paths and Cycles on Surfaces, Éric Colin de Verdičre and Jeff Erickson; Anisotropic Surface Meshing, SiuWing 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; SelfImproving 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 TriangleFreeness 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 CircularArc 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 UnitSpeed Machines are Almost as Powerful as Speedy Machines for Competitive Flow Time Scheduling, HoLeung Chan, TakWah Lam, and KinShing 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 FaultTolerant ConstantDegree 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 IntrinsicDimension Helly Theorem, Jie Gao, Michael Langberg, and Leonard J. Schulman; Finding Large Sticks and Potatoes in Polygons, Olaf HallHolt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, and Arik Sityon; Randomized Incremental Construction of ThreeDimensional 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: AllPairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time, Timothy M. Chan; An O(n log n) Algorithm for Maximum stFlow in a Directed Planar Graph, Glencora Borradaile and Philip Klein; A Simple GAPCanceling 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 DegreeConstrained Partial Orientations, Harold N. Gabow; Session 7A: On the Tandem DuplicationRandom Loss Model of Genome Rearrangement, Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, and Satish Rao; Reducing Tile Complexity for SelfAssembly Through Temperature Programming, MingYang Kao and Robert Schweller; CacheOblivious String Dictionaries, Gerth Střlting Brodal and Rolf Fagerberg; CacheOblivious Dynamic Programming, Rezaul Alam Chowdhury and Vijaya Ramachandran; A Computational Study of ExternalMemory 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 kMulticut Problem, Daniel Golovin, Viswanath Nagarajan, and Mohit Singh; The PrizeCollecting Generalized Steiner Tree Problem Via A New Approach Of PrimalDual Schema, Mohammad Taghi Hajiaghayi and Kamal Jain; 8/7Approximation 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 TwoPlayer 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: ConstantReturns 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 MixedInteger 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 ManCho 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 LiSan 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 BranchWidth, Sangil Oum and Paul Seymour; DAGwidth—Connectivity Measure for Directed Graphs, Jan Obdrzálek; Session 9A: On the Diameter of Eulerian Orientations of Graphs, Laszlo Babai; MaxTolerance Graphs as Intersecton Graphs: Cliques, Cycles, and Recognition, Michael Kaufmann, Jan Kratochvil, Katharina A. Lehmann, and Amarendran R. Subramanian; Subgraph Characterization of Red/BlueSplit 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 CrossingFree 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; QueryEfficient 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 MultiArmed 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 PeertoPeer Networks, David Arthur and Rina Panigraphy; Oblivious Network Design, Anupam Gupta, Mohammad T. Hajiaghayi, and Harald Räcke; The Price of Being NearSighted, 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 FriedmanPippenger Theorem on Tree Embeddings and Applications to Routing, D. Dellamonica, Jr. and Y. Kohayakawa; A Tight Upper Bound on the Probabilistic Embedding of SeriesParallel Graphs, Yuval Emek and David Peleg; Session 11C: SingleValue 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; SingleMinded 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 PassEfficient Algorithms for Clustering, Kevin L. Chang and Ravi Kannan; Correlation Clustering with a Fixed Number of Clusters, Ioannis Giotis and Venkatesan Guruswami; On kMedian Clustering in High Dimensions, Ke Chen; Entropy Based Nearest Neighbor Search in High Dimensions, Rina Panigrahy; Session 12C: A Dynamic Data Structure for 3d Convex Hulls and 2d 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.
2006 / xviii + 1242 pages / Softcover / ISBN13: 9780898716054 / ISBN10: 0898716055 / List Price $156.50 / SIAM Member Price $109.55 / Order Code PR122
