Preface |
Acknowledgments |
[varepsilon]-Approximate Linear Progams: New Bounds and Computation / Daniel BienstockSession 1A: |
Orthogonal Graph Drawing with Constraints / Markus Eiglsperger ; Ulrich Fo[sz ligature]meier ; Michael Kaufmann |
Fast Practical Solution of Sorting by Reversals / Alberto Caprara ; Giuseppe Lancia ; See Kiong Ng |
Commuting with Delay Prone Buses / Mayur Datar ; Abhiram Ranade |
Coloring Non-Uniform Hypergraphs: A New Algorithmic Approach to the General Lovasz Local Lemma / Artur Czumaj ; Christian ScheidelerSession 1B: |
On the Complexity of Bicoloring Clique Hypergraphs of Graphs / J. Kratochvil ; Zs. Tuza |
Weakly Chordal Graph Algorithms via Handles / Ryan B. Hayward ; Jeremy Spinrad ; R. Sritharan |
Recognizing Dart-Free Perfect Graphs / V. Chvatal ; J. Fonlupt ; L. Sun ; A. Zemirline |
An Optimal Algorithm for Hyperplane Depth in the Plane / Stefan Langerman ; William SteigerSession 1C: |
On Heilbronn's Problem in Higher Dimension / Hanno Lefmann |
Finding Minimal Triangulations of Convex 3-Polytopes Is NP-Hard / Alexander Below ; Jesus A. De Loera ; Jurgen Richter-Gebert |
A Point-Placement Strategy for Conforming Delaunay Tetrahedralization / Michael Murphy ; David M. Mount ; Carl W. Gable |
Digraph Minors and Algorithms / Robin ThomasSession 2: |
Cooperative Facility Location Games / Michel X. Goemans ; Martin SkutellaSession 3A: |
K-Medians, Facility Location, and the Chernoff-Wald Bound / Neal E. Young |
Improved Approximation Algorithms for MAX SAT / Takao Asano ; David P. Williamson |
Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems / Robert D. Carr ; Lisa K. Fleischer ; Vitus J. Leung ; Cynthia A. Phillips |
Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem / Robert Carr ; Santosh Vempala |
Typical Random 3-SAT Formulae and the Satisfiability Threshold / Olivier Dubois ; Yacine Boufkhad ; Jacques MandlerSession 3B: |
A Lower Bound for DLL Algorithms for k-SAT / Pavel Pudlak ; Russell Impagliazzo |
On Permutations with Limited Independence / Toshiya Itoh ; Yoshinori Takei ; Jun Tarui |
Min-Wise Versus Linear Independence / Andrei Z. Broder ; Uriel Feige |
Hamiltonicity and Colorings of Arrangement Graphs / Stefan Felsner ; Ferran Hurtado ; Marc Noy ; Ileana Streinu |
Testing and Spot-Checking of Data Streams / J. Feigenbaum ; S. Kannan ; M. Strauss ; M. ViswanathanSession 3C: |
Engineering the Compression of Massive Tables: An Experimental Approach / Adam L. Buchsbaum ; Donald F. Caldwell ; Kenneth W. Church ; Glenn S. Fowler ; S. Muthukrishnan |
On the Temporal HZY Compression Scheme / Z. Cohen ; Y. Matias ; S. C. Sahinalp ; J. Ziv |
Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme / Charles Knessl ; Wojciech Szpankowski |
Communication Complexity of Document Exchange / Graham Cormode ; Mike Paterson ; Suleyman Cenk Sahinalp ; Uzi Vishkin |
Scheduling a Pipelined Operator Graph / Petra Schuurman ; Gerhard J. WoegingerSession 4A: |
A PTAS for the Multiple Knapsack Problem / Chandra Chekuri ; Sanjeev Khanna |
Approximation Algorithms for Data Placement on Parallel Disks / L. Golubchik ; S. Khanna ; S. Khuller ; R. Thurimella ; A. Zhu |
Movement Minimization in Conveyor Flow Shop Processing / W. Espelage ; E. Wanke |
Forcing Relations for AND/OR Precedence Constraints / Rolf H. Mohring ; Frederik Stork |
The Interlace Polynomial: A New Graph Polynomial / Richard Arratia ; Bela Bollobas ; Gregory B. SorkinSession 4B: |
The Complexity of Counting Graph Homomorphisms / Martin Dyer ; Catherine Greenhill |
A Fast Algorithm to Generate Unlabeled Necklaces / Frank Ruskey ; Joe Sawada |
Construction of Visual Secret Sharing Schemes with Almost Optimal Contrast / Christian Kuhlmann ; Hans Ulrich Simon |
Sharing One Secret vs. Sharing Many Secrets: Tight Bounds on the Average Improvement Ratio / Giovanni Di Crescenzo |
Algorithmic Strategies in Combinatorial Chemistry / Deborah Goldman ; Sorin Istrail ; Antonio Piccolboni ; Brian WalenzSession 4C: |
Computing the Quartet Distance Between Evolutionary Trees / David Bryant ; John Tsang ; Paul Kearney ; Ming Li |
A Practical Algorithm for Recovering the Best Supported Edges of an Evolutionary Tree / Vincent Berry ; Tao Jiang ; Todd Wareham ; Haoyong Zhang |
Pattern Discovery on Character Sets and Real-Valued Data: Linear Bound on Irredundant Motifs and an Efficient Polynomial Time Algorithm / Laxmi Parida ; Isidore Rigoutsos ; Aris Floratos ; Dan Platt ; Yuan Gao |
Improved Bounds on the Sample Complexity of Learning / Yi Li ; Philip M. Long ; Aravind Srinivasan |
On Local Search and Placement of Meters in Networks / Samir Khuller ; Randeep Bhatia ; Robert PlessSession 5A: |
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs / Eran Halperin |
An Approximation Algorithm for the Covering Steiner Problem / Goran Konjevod ; R. Ravi |
On the Red-Blue Set Cover Problem / Srinivas Doddi ; Madhav Marathe |
Approximate Congruence In Nearly Linear Time / Piotr Indyk ; Suresh VenkatasubramanianSession 5B: |
Locally Lifting the Curse of Dimensionality for Nearest Neighbor Search / Peter N. Yianilos |
Dimensionality Reduction Techniques for Proximity Problems |
Expected-Case Complexity of Approximate Nearest Neighbor Searching / Sunil Arya ; Ho-Yam Addy Fu |
A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry / Ting Chen ; Ming-Yang Kao ; Matthew Tepel ; John Rush ; George M. ChurchSession 5C: |
Algorithms for Optimizing Production DNA Sequencing / Eva Czabarka ; Madhav V. Marathe ; Allon G. Percus ; David C. Torney |
Estimating DNA Sequence Entropy / J. Kevin Lanctot ; En-hui Yang |
Selective Mapping: A Discrete Optimization Approach to Selecting a Population Subset for Use in a High-Density Genetic Mapping Project / Daniel G. Brown ; Todd J. Vision ; Steven D. Tanksley |
Cutting Planes and the Traveling Salesman Problem / D. Applegate ; R. Bixby ; W. CookSession 6: |
Caching in Networks / Friedhelm Meyer auf der Heide ; Berthold Vocking ; Matthias WestermannSession 7A: |
Instability of FIFO in Session-Oriented Networks / Matthew Andrews |
The Effects of Temporary Sessions on Network Performance / Lisa Zhang |
Randomized Greedy Hot-Potato Routing / Costas Busch ; Maurice Herlihy ; Roger Wattenhofer |
On Deciding Stability of Scheduling Policies in Queueing Systems / David Gamarnik |
Restructuring Ordered Binary Trees / William Evans ; David KirkpatrickSession 7B: |
Faster Deterministic Dictionaries / Rasmus Pagh |
Competitive Tree-Structured Dictionaries / Michael T. Goodrich |
Even Strongly Universal Hashing Is Pretty Fast / Mikkel Thorup |
Word Encoding Tree Connectivity Works / Stephen Alstrup ; Jens Peter Secher |
Algorithms for Minimum Volume Enclosing Simplex in R[superscript 3] / Yunhong Zhou ; Subhash SuriSession 7C: |
Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells / Pankaj K. Agarwal ; Boris Aronov ; Micha Sharir |
Evaluating the Cylindricity of a Nominally Cylindrical Point Set / Olivier Devillers ; Franco P. Preparata |
Approximation Algorithms for Layered Manufacturing / Pavan K. Desikan |
Approximation Algorithms for Projective Clustering / Cecilia M. Procopiuc |
Scheduling to Minimize Average Stretch Without Migration / Luca Becchetti ; Stefano LeonardiSession 8A: |
Minimizing Maximum Response Time in Scheduling Broadcasts / Yair Bartal |
Applying Extra-Resource Analysis to Load Balancing / Mark Brehob ; Eric Torng ; Patchrawat Uthaisombut |
Balancing Steiner Trees and Shortest Path Trees Online / Ashish Goel ; Kamesh Munagala |
Generating Adversaries for Request-Answer Games / Todd Gormley ; Nicholas Reingold ; Jeffery Westbrook |
Maintaining Hierarchical Graph Views / Jeffrey R. WestbrookSession 8B: |
Improved Classification via Connectivity Information / Robert Krauthgamer ; Michael Mitzenmacher |
Efficient Dynamic Traitor Tracing / Omer Berkman ; Michal Parnas ; Jiri Sgall |
Watermarking Maps: Hiding Information in Structured Data / Francis Zane |
Strictly Non-Blocking WDM Cross-Connects / April Rasala ; Gordon Wilfong |
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colourings / Leslie Ann Goldberg ; Mark JerrumSession 8C: |
A Faster Method for Sampling Independent Sets / Mark Huber |
Strong Bias of Group Generators: An Obstacle to the "Product Replacement Algorithm" / Laszlo Babai ; Igor Pak |
Random Three-Dimensional Tilings of Aztec Octahedra and Tetrahedra: An Extension of Domino Tilings / Dana Randall ; Gary Yngve |
An Algebraic Method to Compute a Shortest Path of Local Flips Between Two Tilings / Eric Remila |
Coloring Powers of Planar Graphs / Geir Agnarsson ; Magnus M. HalldorssonSession 9A: |
Directed Network Design with Orientation Constraints / Joseph (Seffi) Naor ; F. Bruce Shepherd |
A (2 + [varepsilon])-Approximation Scheme for Minimum Domination on Circle Graphs / Mirela Damian-lordache ; Sriram V. Pemmaraju |
An Approximation Algorithm for Finding a Long Path in Hamiltonian Graphs / Sundar Vishwanathan |
TSP-Based Curve Reconstruction in Polynomial Time / Ernst Althaus ; Kurt MehlhornSession 9B: |
A Tree-Edit-Distance Algorithm for Comparing Simple, Closed Shapes / Philip Klein ; Srikanta Tirthapura ; Daniel Sharvit ; Ben Kimia |
Computing the Arrangement of Curve Segments: Divide-and-Conquer Algorithms via Sampling / Nancy M. Amato ; Edgar A. Ramos |
Optimizing the Sum of Linear Fractional Functions and Applications / Danny Z. Chen ; Ovidiu Daescu ; Yang Dai ; Naoki Katoh ; Xiaodong Wu ; Jinhui Xu |
Edge-Disjoint Paths in Expander Graphs / Alan M. FriezeSession 9C: |
Escaping a Grid by Edge-Disjoint Paths / Wun-Tat Chan ; Francis Y. L. Chin ; Hing-Fung Ting |
Fast Randomized Algorithms for Computing Minimum (3,4,5,6)-Way Cuts / Matthew S. Levine |
Adaptive Set Intersections, Unions, and Differences / Erik D. Demaine ; Alejandro Lopez-Ortiz ; J. Ian Munro |
The Whole Genome Assembly of Drosophila / Gene MyersSession 10: |
A 2 + [varepsilon] Approximation Algorithm for the k-MST Problem / Sanjeev Arora ; George KarakostasSession 11A: |
The Prize Collecting Steiner Tree Problem: Theory and Practice / David S. Johnson ; Maria Minkoff ; Steven Phillips |
Improved Steiner Tree Approximation in Graphs / Gabriel Robins ; Alexander Zelikovsky |
The Rectilinear Steiner Arborescence Problem Is NP-Complete / Weiping Shi ; Chen Su |
Improved Bandwidth Approximation for Trees / Anupam Gupta |
Faster Algorithms for String Matching with k Mismatches / Amihood Amir ; Moshe Lewenstein ; Ely PoratSession 11B: |
On the Shared Substring Alignment Problem / Gad M. Landau ; Michal Ziv-Ukelson |
Real Scaled Matching / Ayelet Butman |
Inplace Run-Length 2d Compressed Search / Dina Sokol |
Pattern Matching in Dynamic Texts / Gerth Stolting Brodal ; Theis Rauhe |
Towards a Theory of Cache-Efficient Algorithms / Sandeep Sen ; Siddhartha ChatterjeeSession 11C: |
Efficient Bundle Sorting / Yossi Matias ; Eran Segal ; Jeffrey Scott Vitter |
Fast Concurrent Access to Parallel Disks / Peter Sanders ; Sebastian Egner ; Jan Korst |
On External Memory Graph Traversal / Michael Goldwasser ; Jeffery R. Westbrook |
Deterministic Broadcasting in Unknown Radio Networks / Bogdan S. Chlebus ; Leszek Gasieniec ; Alan Gibbons ; Andrzej Pelc ; Wojciech Rytter |
New and Improved Algorithms for Minsum Shop Scheduling / Maurice Queyranne ; Maxim SviridenkoSession 12A: |
Off-Line Admission Control for General Scheduling Problems / R. N. Uma ; Joel Wein |
Approximating the Maximum Quadratic Assignment Problem / Esther M. Arkin ; Refael Hassin |
Accurate Approximations for Asian Options / Donald Aingworth ; Rajeev Motwani ; Jeffrey D. Oldham |
Finite-Resolution Hidden Surface Removal / Jeff EricksonSession 12B: |
On Incremental Rendering of Silhousette Maps of a Polyhedral Scene / Alon Efrat ; Leonidas J. Guibas ; Olaf A. Hall-Holt ; Li Zhang |
Computing Contour Trees in All Dimensions / Hamish Carr ; Jack Snoeyink ; Ulrike Axen |
Sweeping Simple Polygons with a Chain of Guards / Sariel Har-Peled ; David C. Lin ; Joseph S. B. Mitchell ; T. M. Murali |
Finding the Closest Lattice Vector When It's Unusually Close / Session 12C: |
A New Bound for the Caratheodory Rank of the Bases of a Matroid / J. C. de Pina ; J. Soares |
Minimum Ratio Canceling Is Oracle Polynomial for Linear Programming, But Not Strongly Polynomial, Even for Networks / S. Thomas McCormick ; Akiyoshi Shioura |
Nearly Optimal Computations with Structured Matrices / Victor Y. Pan |
Author Index |
Preface |
Acknowledgments |
[varepsilon]-Approximate Linear Progams: New Bounds and Computation / Daniel BienstockSession 1A: |