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

Cover
SIAM Activity Group on Discrete Mathematics, Association for Computing Machinery, Society for Industrial and Applied Mathematics
SIAM, 01.01.2006 - 1242 Seiten
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 Jurdzinski, 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 Patrascu; 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, Tugkan Batu, Funda Ergun, and Cenk Sahinalp0898716012\\This comprehensive book not only introduces the C and C++ programming languages but also shows how to use them in the numerical solution of partial differential equations (PDEs). It leads the reader through the entire solution process, from the original PDE, through the discretization stage, to the numerical solution of the resulting algebraic system. The well-debugged and tested code segments implement the numerical methods efficiently and transparently. Basic and advanced numerical methods are introduced and implemented easily and efficiently in a unified object-oriented approach.
 

Was andere dazu sagen - Rezension schreiben

Es wurden keine Rezensionen gefunden.

Inhalt

Session
1
A Simple 020288 Independent Set Algorithm
18
A Polynomial Algorithm to Find an Independent Set of Maximum Weight in
26
Session 18
41
Directed Metrics and Directed Graph Partitioning Problems
51
Improved Embeddings of Graph Metrics into Random Trees
61
Small HopDiameter Sparse Spanners tor Doubling Metrics
70
Contents
73
Session
611
Approximating the kMulticut Problem
621
63 The PrizeCollecting Generalized Steiner Tree Problem via a New Approach
631
Piotr Berman and Marek Karpinski
641
Improved Lower and Upper Bounds for Universal TSP in Planar Metrics
649
Leontief Economies Encode Nonzero Sum TwoPlayer Games
659
The Complexity of Quantitative Concurrent Parity Games
678
Session
698

Metric Cotype
79
Session
89
Approximating Unique Games
99
Computing Sequential Equilibria tor TwoPlayer Games
107
Contents
117
Finding Nucleolus of Flow Game
124
Invited Plenary Abstract
132
An Asymptotic Approximation Algorithm for 3DStrip Packing
143
Facility Location with Hierarchical Facility Costs
153
Approximability of the Unique Coverage Problem
162
Computing Steiner Minimum Trees in Hamming Metric
172
Session 38
182
Tightening NonSimple Paths and Cycles on Surfaces
192
Anisotropic Surface Meshing
202
Simultaneous Diagonal Flips in Plane Triangulations
212
Morphing Orthogonal Planar Graph Drawings
222
Session 30
231
On the Capacity of Information Networks
241
Lower Bounds for Asymmetric Communication Channels and Distributed Source
251
SelfImproving Algorithms
261
27 Cake Cutting Really Is Not a Piece of Cake
271
Session
279
Constraint Solving via Fractional Edge Covers
289
Testing Graph lsomorphism
299
Efficient Construction of Unit CircularArc Models
309
On the Chromatic Number of Some Geometric Hypergraphs
316
Session 48
324
Extra UnitSpeed Machines Are Almost as Powerful as Speedy Machines
334
Improved Approximation Algorithms for Broadcast Scheduling
344
Distributed Selfish Load Balancing
354
A Polynomial Time
364
A Tool tor Text indexing
368
A FaultTolerant ConstantDegree Distributed Data
384
implicit Dictionaries with 01 Modiiications per Update and Fast Search
404
Asymmetric Balanced Allocation with Simple Hash Functions
424
Superiority and Complexity of the Spaced Seeds
444
Session
464
Randomized Incremental Constructions ot ThreeDimensional Convex Hulls
484
On the Number of Plane Graphs
504
AllPairs Shortest Paths lor Unweighted Undirected Graphs in 0 mn Time
514
An On log n Algorithm for Maximum stFlow in a Directed Planar Graph
524
A Simple GAPCanceling Algorithm for the Generalized Maximum Flow Problem
534
Four Point Conditions and Exponential Neighborhoods tor Symmetric
544
Upper DegreeConstrained Partial Orientations
554
Session
564
Contents
569
CacheOblivious String Dictionaries
581
CacheOblivious Dynamic Programming
591
A Computational Study of ExternalMemory BFS Algorithms
601
Trading Off Space for Passes in Graph Streaming Problems
714
Streaming and Sublinear Approximation of Entropy and Information Distances
733
Linear Programming and Unique Sink Orientations
749
A Semidefrnite Programming Approach to Tensegrity Theory and Realizability
766
Weighted Isotonic Regression under the L Norm
783
Obvlivious String Embeddings and Edit Distance Approximations
792
Spanners and Emulators with Sublinear Distance Errors
802
Certifying Large BranchWidth
810
Session
822
Cliques Cycles and Recognition
832
Subgraph Characterization of RedBlueSplit Graphs and Konig Egervary Graphs
842
Critical Chromatic Number and the Complexity of Perfect Packings in Graphs
851
On the Number of CrossingFree Matchings Cycles and Partitions
860
Session 98
870
Quantum Verification of Matrix Products
880
Counting without Sampling New Algorithms for Enumeration Problems Using
890
Accelerating Simulated Annealing tor the Permanent and Combinatorial
900
QueryEfficient Algorithms for Polynomial Interpolation over Composites
908
Hajiaghayi Robert D Kleinberg Tom Leighton and Harald Racke
918
Anytime Algorithms for MultiArmed Bandit Problems
928
Less Regret in Online Geometric Optimization Against
937
On the Competitive Ratio of Evaluating Priced Functions
944
Randomized Online Algorithms for Minimum Metric Bipartite Matching
954
Invited Plenary Abstract
960
Oblivious Network Design
970
The Price of Being NearSighted
980
Scalable Leader Election
990
Deterministic Boundary Recognition and Topology Extraction for Large Sensor
1000
Session 118
1010
Moses Charikar Mohammad Taghi Hajiaghayi Howard Karloff and Satsh
1018
Trees and Markov Convexity
1028
An Algorithmic FriedmanPippenger Theorem on Tree Embeddings
1038
Session
1054
An improved Approximation Algorithm tor Combinatorial Auctions with
1064
Revenue Maximization When Bidders Have Budgets
1074
Patrick Briest and Piotr Krysta
1093
Session
1103
Relating Singular Values and Discrepancy of Weighted Directed Graphs
1112
Sampling Algorithms for l2 Regression and Applications
1127
On Maximizing Statistical Discrepancy
1137
Session 128
1147
The Space Complexity of PassEfficient Algorithms for Clustering
1157
Correlation Clustering with a Fixed Number of Clusters
1167
H77 On kMedian Clustering in High Dimensions
1177
Session
1196
I213 Many Distances in Planar Graphs
1213
Kunihiko Sadokane and Roberto Grossi
1230
Urheberrecht

Häufige Begriffe und Wortgruppen

Bibliografische Informationen