Algorithms - ESA 2001

Invited Talks.- External Memory Data Structures.- Some Algorithmic Problems in Large Networks.- Exact and Approximate Distances in Graphs — A Survey.- Caching and Prefetching.- Strongly Competitive Algorithms for Caching with Pipelined Prefetching.- Duality between Prefetching and Queued Writing with Parallel Disks.- Online Algorithms.- Online Bin Coloring.- A General Decomposition Theorem for the k-Server Problem.- Buying a Constant Competitive Ratio for Paging.- Data Structures I.- Simple Minimal Perfect Hashing in Less Space.- Cuckoo Hashing.- Optimization and Approximation.- Coupling Variable Fixing Algorithms for the Automatic Recording Problem.- Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints.- On the Approximability of the Minimum Test Collection Problem.- Sequences.- Finding Approximate Repetitions under Hamming Distance.- SNPs Problems, Complexity, and Algorithms.- Scheduling.- A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs.- Grouping Techniques for Scheduling Problems: Simpler and Faster.- A 2-Approximation Algorithm for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times.- Shortest Paths.- A Simple Shortest Path Algorithm with Linear Average Time.- A Heuristic for Dijkstra’s Algorithm with Many Targets and Its Use in Weighted Matching Algorithms.- Geometry I.- A Separation Bound for Real Algebraic Expressions.- Property Testing with Geometric Queries.- Smallest Color-Spanning Objects.- Data Structures II.- Explicit Deterministic Constructions for Membership in the Bitprobe Model.- Lossy Dictionaries.- Geometry II.- Splitting a Delaunay Triangulation in Linear Time.- A Fast Algorithm for Approximating the Detour of a Polygonal Chain.- An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee.- Distributed Algorithms.- Distributed O(? log n)-Edge-Coloring Algorithm.- Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation.- Graph Algorithms.- Computing Cycle Covers without Short Cycles.- A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth.- Lower Bounds and Exact Algorithms for the Graph Partitioning Problem Using Multicommodity Flows.- Pricing.- Fast Pricing of European Asian Options with Provable Accuracy: Single-Stock and Basket Options.- Competitive Auctions for Multiple Digital Goods.- Broadcasting and Multicasting.- Algorithms for Efficient Filtering in Content-Based Multicast.- Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode.- Round Robin Is Optimal for Fault-Tolerant Broadcasting on Wireless Networks.- Graph Labeling and Graph Drawing.- Online and Offline Distance Constrained Labeling of Disk Graphs.- Approximate Distance Labeling Schemes.- On the Parameterized Complexity of Layered Graph Drawing.- Graphs.- A General Model of Undirected Web Graphs.- Packing Cycles and Cuts in Undirected Graphs.- Greedy Algorithms for Minimisation Problems in Random Regular Graphs.