| Invited Lectures | |
| Solving Traveling Salesman Problems | p. 1 |
| Computing Shapes from Point Cloud Data | p. 2 |
| Mechanism Design for Fun and Profit | p. 3 |
| On Distance Oracles and Routing in Graphs | p. 4 |
| Contributed Papers | |
| Kinetic Medians and fed-Trees | p. 5 |
| Range Searching in Categorical Data: Colored Range Searching on Grid | p. 17 |
| Near-Linear Time Approximation Algorithms for Curve Simplification | p. 29 |
| Translating a Planar Object to Maximize Point Containment | p. 42 |
| Approximation Algorithms for fe-Line Center | p. 54 |
| New Heuristics and Lower Bounds for the Min-Max fe-Chinese Postman Problem | p. 64 |
| SCIL - Symbolic Constraints in Integer Linear Programming | p. 75 |
| Implementing I/O-efficient Data Structures Using TPIE | p. 88 |
| On the fe-Splittable Flow Problem | p. 101 |
| Partial Alphabetic Trees | p. 114 |
| Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router | p. 126 |
| Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy | p. 139 |
| Two Simplified Algorithms for Maintaining Order in a List | p. 152 |
| Efficient Tree Layout in a Multilevel Memory Hierarchy | p. 165 |
| A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons | p. 174 |
| TSP with Neighborhoods of Varying Size | p. 187 |
| 1.375-Approximation Algorithm for Sorting by Reversals | p. 200 |
| Radio Labeling with Pre-assigned Frequencies | p. 211 |
| Branch-and-Bound Algorithms for the Test Cover Problem | p. 223 |
| Constructing Plane Spanners of Bounded Degree and Low Weight | p. 234 |
| Eager st-Ordering | p. 247 |
| Three-Dimensional Layers of Maxima | p. 257 |
| Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy | p. 270 |
| Geometric Algorithms for Density-Based Data Clustering | p. 284 |
| Balanced-Replication Algorithms for Distribution Trees | p. 297 |
| Butterflies and Peer-to-Peer Networks | p. 310 |
| Estimating Rarity and Similarity over Data Stream Windows | p. 323 |
| Efficient Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels | p. 335 |
| Frequency Estimation of Internet Packet Streams with Limited Space | p. 348 |
| Truthful and Competitive Double Auctions | p. 361 |
| Optimal Graph Exploration without Good Maps | p. 374 |
| Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee | p. 387 |
| Non-independent Randomized Rounding and an Application to Digital Halftoning | p. 399 |
| Computing Homotopic Shortest Paths Efficiently | p. 411 |
| An Algorithm for Dualization in Products of Lattices and Its Applications | p. 424 |
| Determining Similarity of Conformational Polymorphs | p. 436 |
| Minimizing the Maximum Starting Time On-line | p. 449 |
| Vector Assignment Problems: A General Framework | p. 461 |
| Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice | p. 473 |
| Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique | p. 485 |
| Online Companion Caching | p. 499 |
| Deterministic Communication in Radio Networks with Large Labels | p. 512 |
| A Primal Approach to the Stable Set Problem | p. 525 |
| Wide-Sense Nonblocking WDM Cross-Connects | p. 538 |
| Efficient Implementation of a Minimal Triangulation Algorithm | p. 550 |
| Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial-Time Approximation Scheme | p. 562 |
| The Probabilistic Analysis of a Greedy Satisfiability Algorithm | p. 574 |
| Dynamic Additively Weighted Voronoi Diagrams in 2D | p. 586 |
| Time-Expanded Graphs for Flow-Dependent Transit Times | p. 599 |
| Partially-Ordered Knapsack and Applications to Scheduling | p. 612 |
| A Software Library for Elliptic Curve Cryptography | p. 625 |
| Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows | p. 637 |
| Randomized Approximation Algorithms for Query Optimization Problems on Two Processors | p. 649 |
| Covering Things with Things | p. 662 |
| On-Line Dial-a-Ride Problems under a Restricted Information Model | p. 674 |
| Approximation Algorithm for the Maximum Leaf Spanning Tree Problem for Cubic Graphs | p. 686 |
| Engineering a Lightweight Suffix Array Construction Algorithm | p. 698 |
| Complexity of Compatible Decompositions of Eulerian Graphs and Their Transformations | p. 711 |
| External-Memory Breadth-First Search with Sublinear I/O | p. 723 |
| Frequency Channel Assignment on Planar Networks | p. 736 |
| Design and Implementation of Efficient Data Types for Static Graphs | p. 748 |
| An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem | p. 760 |
| A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options | p. 772 |
| Sorting 13 Elements Requires 34 Comparisons | p. 785 |
| Extending Reduction Techniques for the Steiner Tree Problem | p. 795 |
| A Comparison of Multicast Pull Models | p. 808 |
| Online Scheduling for Sorting Buffers | p. 820 |
| Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes | p. 833 |
| Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design | p. 845 |
| Minimizing Makespan and Preemption Costs on a System of Uniform Machines | p. 859 |
| Minimizing the Total Completion Time On-line on a Single Machine, Using Restarts | p. 872 |
| High-Level Filtering for Arrangements of Conic Arcs | p. 884 |
| An Approximation Scheme for Cake Division with a Linear Number of Cuts | p. 896 |
| A Simple Linear Time Algorithm for Finding Even Triangulations of 2-Connected Bipartite Plane Graphs | p. 902 |
| Author Index | p. 915 |
| Table of Contents provided by Publisher. All Rights Reserved. |
