| 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： |
図書
