Preface |
Acknowledgments |
In Memoriam |
Optimal Parallel Selection / Yijie HanSession 1A: |
Selection with Monotone Comparison Costs / Sampath Kannan ; Sanjeev Khanna |
Property Testing of Data Dimensionality / Robert Krauthgamer ; Ori Sasson |
Comparing Top K Lists / Ronald Fagin ; Ravi Kumar ; D. Sivakumar |
Algorithms for Power Savings / Sandy Irani ; Sandeep Shukla ; Rajesh GuptaSession 1B: |
Dynamic TCP Acknowledgement: Penalizing Long Delays / Susanne Albers ; Helge Bals |
Approximately Optimal Control of Fluid Networks / Lisa Fleischer ; Jay Sethuraman |
Minimum Cost Flows over Time without Intermediate Storage / Martin Skutella |
Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle / Michael Elkin ; Guy KortsarzSession 1C: |
On the Performance of User Equilibria in Traffic Networks / Andreas S. Schulz ; Nicolas Stier Moses |
Faster Approximation Algorithms for the Minimum Latency Problem / Aaron Archer ; David P. Williamson |
Data Migration to Minimize the Average Completion Time / Yoo-Ah Kim |
Invited Plenary Abstract / Session 2: |
Browsing around a Digital Library / Ian H. Witten |
Binary Space Partitions for 3D Subdivisions / John Hershberger ; Subhash SuriSession 3A: |
Allocating Vertex [pi]-Guards in Simple Polygons via Pseudo-triangulations / Bettina Speckmann ; Csaba D. Toth |
Straight-Skeleton Based Contour Interpolation / Gill Barequet ; Michael T. Goodrich ; Aya Levi-Steiner ; Dvir Steiner |
Mobius-Invariant Natural Neighbor Interpolation / Marshall Bern ; David Eppstein |
Improved Bounds on the Average Length of Longest Common Subsequences / George S. LuekerSession 3B: |
Directed Scale-Free Graphs / Bela Bollobas ; Christian Borgs ; Jennifer Chayes ; Oliver Riordan |
The Cover Time of Sparse Random Graphs / Colin Cooper ; Alan Frieze |
Perfect Matchings in Random Graphs with Prescribed Minimal Degree / Boris Pittel |
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs / Dieter Kratsch ; Ross M. McConnell ; Kurt Mehlhorn ; Jeremy P. SpinradSession 3C: |
Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up / Fedor V. Fomin ; Dimitrios M. Thilikos |
Quick and Good Facility Location / Mikkel Thorup |
Chain Decompositions and Independent Trees in 4-Connected Graphs / Sean Curran ; Orlando Lee ; Xingxing Yu |
Optimizing Misdirection / Piotr Berman ; Piotr KrystaSession 4A: |
Online Learning in Online Auctions / Avrim Blum ; Vijay Kumar ; Atri Rudra ; Felix Wu |
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents / Christos Papadimitriou ; Kunal Talwar ; Eva Tardos |
Competitiveness via Consensus / Andrew V. Goldberg ; Jason D. Hartline |
Pass Efficient Algorithms for Approximating Large Matrices / Petros Drineas ; Ravi KannanSession 4B: |
Rangesum Histograms / S. Muthukrishnan ; Martin Strauss |
Approximation of Functions over Redundant Dictionaries Using Coherence / Anna C. Gilbert ; Martin J. Strauss |
Counting Inversions in Lists / Anupam Gupta ; Francis X. Zane |
Certifying and Repairing Solutions to Large LPs: How Good Are LP-Solvers? / Marcel Dhiflaoui ; Stefan Funke ; Carsten Kwappik ; Michael Seel ; Elmar Schomer ; Ralph Schulte ; Dennis WeberSession 4C: |
An Improved Approximation Algorithm for the O-Extension Problem / Jittat Fakcharoenphol ; Chris Harrelson ; Satish Rao |
Packing Steiner Trees / Kamal Jain ; Mohammad Mahdian ; Mohammad R. Salavatipour |
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees / Eran Halperin ; Aravind Srinivasan ; Nan Wang |
The Flow Complex: A Data Structure for Geometric Modeling / Joachim Giesen ; Matthias JohnSession 5A: |
Graded Conforming Delaunay Tetrahedralization with Bounded Radius-Edge Ratio / Siu-Wing Cheng ; Sheung-Hung Poon |
On the Combinatorial Complexity of Euclidean Voronoi Cells and Convex Hulls of d-Dimensional Spheres / Jean-Daniel Boissonnat ; Menelaos I. Karavelas |
Perturbations and Vertex Removal in a 3D Delaunay Triangulation / Olivier Devillers ; Monique Teillaud |
Root Comparison Techniques Applied to Computing the Additively Weighted Voronoi Diagram / Ioannis Z. Emiris |
Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources / Mary Cryan ; Martin Dyer ; Haiko Muller ; Leen StougieSession 5B: |
Smaller Explicit Superconcentrators / N. Alon ; M. Capalbo |
A (1 + [epsilon])-Approximation Algorithm for Partitioning Hypergraphs Using a New Algorithmic Version of the Lovasz Local Lemma |
A Spectral Technique for Random Satisfiable 3CNF Formulas / Abraham Flaxman |
Random MAX SAT, Random MAX CUT, and Their Phase Transitions / Don Coppersmith ; David Gamarnik ; Mohammad Hajiaghayi ; Gregory B. Sorkin |
Space-Efficient Finger Search on Degree-Balanced Search Trees / Guy E. Blelloch ; Bruce M. Maggs ; Shan Leung Maverick WooSession 5C: |
Skip Graphs / James Aspnes ; Gauri Shah |
Maintaining All-Pairs Approximate Shortest Paths under Deletion of Edges / Surender Baswana ; Ramesh Hariharan ; Sandeep Sen |
A Faster and Simpler Fully Dynamic Transitive Closure / Liam Roditty |
Data Streams: Algorithms and Applications / Session 6: |
Sparse Distance Preservers and Additive Spanners / Session 7A: |
Multi-Embedding and Path Approximation of Metric Spaces / Yair Bartal ; Manor Mendel |
Approximation Algorithm for Embedding Metrics into a Two-Dimensional Space / Mihai Badoiu |
On the Complexity of Distance-Based Evolutionary Tree Reconstruction / Valerie King ; Li Zhang ; Yunhong Zhou |
Improved Results for Directed Multicut / Session 7B: |
Algorithms for k-Colouring and Finding Maximal Independent Sets / Jesper Makholm Byskov |
Equitable Colorings with Constant Number of Colors / S. V. Pemmaraju ; K. Nakprasit ; A. V. Kostochka |
Better Performance Bounds for Finding the Smallest k-Edge Connected Spanning Subgraph of a Multigraph / Harold N. Gabow |
A Note on the Set Systems Used for Broadcast Encryption / Alexander RussellSession 7C: |
Lower Bounds for Collusion-Secure Fingerprinting / Chris Peikert ; Abhi Shelat ; Adam Smith |
Quantum Property Testing / Harry Burhman ; Lance Fortnow ; Ilan Newman ; Hein Rohrig |
Quantum Algorithms for Some Hidden Shift Problems / Wim van Dam ; Sean Hallgren ; Lawrence Ip |
Simulataneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk / Ashish Goel ; Deborah EstrinSession 8A: |
Non-independent Randomized Rounding / Benjamin Doerr |
Minimizing Weighted Flow Time / N. Bansal ; K. Dhamdhere |
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-Perfect Graph / Friedrich Eisenbrand ; Naveen Garg ; Jochen Konemann |
Lower Bounds for Embedding Edit Distance into Normed Spaces / A. Andoni ; M. Deza ; A. Gupta ; P. Indyk ; S. RaskhodnikovaSession 8B: |
Embedding k-Outerplanar Graphs into l[subscript 1] / Chandra Chekuri ; Yuri Rabinovich ; Alistair Sinclair |
Embeddings and Non-approximability of Geometric Problems / Venkatesan Guruswami ; Piotr Indyk |
Better Algorithms for High-Dimensional Proximity Problems via Asymmetric Embeddings / Session 8C: |
Lower Bounds for External Memory Dictionaries / Gerth Stolting Brodal ; Rolf Fagerberg |
Online Paging with Arbitrary Associativity / Enoch Peserico |
The Set-Associative Cache Performance of Search Trees / James D. Fix |
Computing Strongly Connected Components in a Linear Number of Symbolic Steps / Raffaella Gentilini ; Carla Piazza ; Alberto Policriti |
On the Rectilinear Crossing Number of Complete Graphs / Uli WagnerSession 9A: |
Matching Planar Maps / Helmut Alt ; Alon Efrat ; Gunter Rote ; Carola Wenk |
Dynamic Generators of Topologically Embedded Graphs |
Computing Homotopic Shortest Paths in the Plane / Sergei Bespamyatnikh |
Fully-Dynamic Two Dimensional Orthogonal Range and Line Segment Intersection Reporting in Logarithmic Time / Christian Worm Mortensen |
Edge Disjoint Paths Revisited / Session 9B: |
A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality / Markus Blaser |
Approximating Asymmetric Maximum TSP / Moshe Lewenstein ; Maxim Sviridenko |
The k-Traveling Repairman Problem |
Directed Graphs Requiring Large Numbers of Shortcuts / William Hesse |
Implicit Dictionaries Supporting Searches and Amortized Updates in O(log n log log n) Time / Gianni Franceschini ; Roberto GrossiSession 9C: |
Compact Representations of Separable Graphs / Daniel K. Blandford ; Ian A. Kash |
Labeling Schemes for Small Distances in Trees / Stephen Alstrup ; Philip Bille ; Theis Rauhe |
On AC[superscript 0] Implementations of Fusion Trees and Atomic Heaps |
Who Cares about Permanents? / Persi DiaconisSession 10: |
Between O(nm) and O(n[superscript alpha]) / Jeremy SpinradSession 11A: |
Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons / Devdatt Dubhashi ; Alessandro Mei ; Alessandro Panconesi ; Jaikumar Radhakrishnan |
A 5/4-Approximation Algorithm for Minimum 2-Edge-Connectivity / Raja Jothi ; Balaji Raghavachari ; Subramanian Varadarajan |
Fault-Tolerant Facility Location / Chaitanya Swamy ; David B. Shmoys |
Efficient Sequences of Trials / Edith Cohen ; Amos Fiat ; Haim KaplanSession 11B: |
Pursuit-Evasion with Imprecise Target Location / Gunther Rote |
Unconditional Proof of Tightness of Johnson Bound / Vendatesan Guruswami ; Igor Shparlinski |
Deterministic Identity Testing for Multivariate Polynomials / Richard Lipton ; Nisheeth Vishnoi |
Competitive Queueing Policies for QoS Switches / Nir Andelman ; Yishay Mansour ; An ZhuSession 11C: |
Dynamic Routing on Networks with Fixed-Size Buffers / William Aiello ; Rafail Ostrovsky ; Eyal Kushilevitz ; Adi Rosen |
Dynamic Construction of Bluetooth Scatternets of Fixed Degree and Low Diameter / Lali Barriere ; Pierre Fraigniaud ; Lata Narayanan ; Jaroslav Opatrny |
Scheduling Techniques for Media-on-Demand / Amotz Bar-Noy ; Richard E. Ladner ; Tami Tamir |
Smaller Core-Sets for Balls / Mihal Badoiu ; Kenneth L. ClarksonSession 12A: |
Zonotopes as Bounding Volumes / Leonidas J. Guibas ; An Nguyen |
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree / Artur Czumaj ; Funda Ergun ; Avner Magen ; Ronitt Rubinfeld ; Christian Sohler |
An Approximation Algorithm for Cutting Out Convex Polygons / Adrian Dumitrescu |
Inferring Tree Topologies Using Flow Tests / Torsten Suel ; Radek VingralekSession 12B: |
Wavelength Assignment and Generalized Interval Graph Coloring / Peter Winkler ; Lisa Zhang |
An Improved Approximation Algorithm for the Partial Latin Square Extension Problem / Carla P. Gomes ; Rommel G. Regis |
Multirate Rearrangeable Clos Networks and a Generalized Edge Coloring Problem on Bipartite Graphs / Hung Q. Ngo ; Van H. Vu |
High-Order Entropy-Compressed Text Indexes / Ankur Gupta ; Jeffrey Scott VitterSession 12C: |
Multidimensional Matching and Fast Search in Suffix Trees / Richard Cole |
Inplace 2D Matching in Compressed Images / Amihood Amir ; Gad M. Landau ; Dina Sokol |
The Similarity Metric / Ming Li ; Xin Chen ; Xin Li ; Bin Ma ; Paul Vitanyi |
Author Index |
Preface |
Acknowledgments |
In Memoriam |
Optimal Parallel Selection / Yijie HanSession 1A: |
Selection with Monotone Comparison Costs / Sampath Kannan ; Sanjeev Khanna |
Property Testing of Data Dimensionality / Robert Krauthgamer ; Ori Sasson |