9th Annual European Symposium on Algorithms ESA 2001 BRICS, University of Aarhus, Denmark, August 28-31, 2001 List of accepted papers (in random order, really) http://www.brics.dk/esa2001/ ------------------------------------------------------------------- Online Bin-Coloring Sven Oliver Krumke and Willem de Paepe and Joerg Rambau and Leen Stougie ------------------------------------------------------------------- Fast Pricing of European Asian Options with Provable Accuracy: Single-stock and Basket Options Karhan Akcoglu and Ming-Yang Kao and Shuba V. Raghavan ------------------------------------------------------------------- A Heuristic for Dijkstra's Algorithm with Many Targets and its Use in Weighted Matching Algorithms Kurt Mehlhorn and Guido Schaefer ------------------------------------------------------------------- A General Decomposition Theorem for the k-Server Problem Steve Seiden ------------------------------------------------------------------- Approximation algorithms for scheduling malleable tasks under precedence constraints R. Lepere and D. Trystram and G.J. Woeginger ------------------------------------------------------------------- Strongly Competitive Algorithms for Caching with Pipelined Prefetching Alexander Gaysinsky and Alon Itai and Hadas Shachnai ------------------------------------------------------------------- Computing Cycle Covers without Short Cycles Markus Blaeser and Bodo Siebert ------------------------------------------------------------------- Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation John Douceur and Roger Wattenhofer ------------------------------------------------------------------- A Separation Bound for Real Algebraic Expressions Christoph Burnikel and Stefan Funke and Kurt Mehlhorn and Stefan Schirra and Susanne Schmitt ------------------------------------------------------------------- A FPTAS for approximating the unrelated parallel machines scheduling problem with costs E. Angel and E. Bampis and A. Kononov ------------------------------------------------------------------- Buying a constant competitive ratio for paging J. Csirik and C. Imreh and J. Noga and S. Seiden and G. Woeginger ------------------------------------------------------------------- Splitting a Delaunay triangulation in linear time Bernard Chazelle and Olivier Devillers and Ferran Hurtado and Merce Mora and Vera Sacristan and Monique Teillaud ------------------------------------------------------------------- A Simple Shortest Path Algorithm with Linear Average Time Andrew V. Goldberg ------------------------------------------------------------------- A fast algorithm for approximating the detour of a polygonal chain Annette Ebbers-Baumann and Rolf Klein and Elmar Langetepe and Andrzej Lingas ------------------------------------------------------------------- Algorithms for Efficient Filtering in Content-Based Multicast Rahul Shah and Stefan Langerman and Sachin Lodha ------------------------------------------------------------------- On the Approximability of the Minimum Test Collection Problem B.V. Halldorsson and M.M. Halldorsson and R. Ravi ------------------------------------------------------------------- Finding approximate repetitions under Hamming distance Roman Kolpakov and Gregory Kucherov ------------------------------------------------------------------- Simple minimal perfect hashing in less space Martin Dietzfelbinger and Torben Hagerup ------------------------------------------------------------------- A general model of web graphs Colin Cooper and Alan Frieze ------------------------------------------------------------------- Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode Pierre Fraigniaud ------------------------------------------------------------------- On-line and Off-line distance constrained labeling of disk graphs Jiri Fiala and Aleksei V. Fishkin and Fedor V. Fomin ------------------------------------------------------------------- Smallest Color-Spanning Objects Manuel Abellanas and Ferran Hurtado and Christian Icking and Rolf Klein and Elmar Langetepe and Lihong Ma and Belen Palop and Vera Sacristan ------------------------------------------------------------------- A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth Dimitrios M. Thilikos and Maria Serna and Hans L. Bodlaender ------------------------------------------------------------------- Lossy Dictionaries Rasmus Pagh and Flemming Friche Rodler ------------------------------------------------------------------- Cuckoo Hashing Rasmus Pagh and Flemming Friche Rodler ------------------------------------------------------------------- An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee Stephan Eidenbenz and Peter Widmayer ------------------------------------------------------------------- On the Parameterized Complexity of Layered Graph Drawing V. Dujmovic and M. Fellows and M. Hallett and M. Kitching and G. Liotta and C. McCartin and N. Nishimura and P. Ragde and F. Rosamond and M. Suderman and S. Whitesides and D. R. Wood ------------------------------------------------------------------- Grouping techniques for scheduling problems: simpler and faster Aleksei V. Fishkin and Klaus Jansen and Monaldo Mastrolilli ------------------------------------------------------------------- Lower Bounds and Exact Algorithms for the Graph Partitioning Problem using Multicommodity Flows Norbert Sensen ------------------------------------------------------------------- Distributed O(Delta log n)-edge-coloring algorithm A. Czygrinow and M. Hanckowiak and M. Karonski ------------------------------------------------------------------- Property Testing with Geometric Queries Artur Czumaj and Christian Sohler ------------------------------------------------------------------- Coupling Variable Fixing Algorithms for the Automatic Recording Problem Meinolf Sellmann and Torsten Fahle ------------------------------------------------------------------- Greedy algorithms for minimisation problems in random regular graphs Michele Zito ------------------------------------------------------------------- A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times Y. Karuno and H. Nagamochi ------------------------------------------------------------------- Round Robin is Optimal for Fault-Tolerant Broadcasting on Wireless Networks A. Clementi and A. Monti and and R. Silvestri ------------------------------------------------------------------- Packing Cycles and Cuts in Undirected Graphs Alberto Caprara and Alessandro Panconesi and Romeo Rizzi ------------------------------------------------------------------- SNPs Problems, Complexity and Algorithms Giuseppe Lancia, Vineet Bafna, Sorin Istrail, Ross Lippert and Russell Schwartz ------------------------------------------------------------------- Duality Between Prefetching and Queued Writing with Applications to Integrated Caching and Prefetching and to External Sorting David A. Hutchinson and Peter Sanders and Jeffrey Scott Vitter ------------------------------------------------------------------- Explicit Deterministic Constructions for Set Membership in Bitprobe Model Jaikumar Radhakrishnan and Venkatesh Raman and S. Srinivasa Rao ------------------------------------------------------------------- Approximate Distance Labeling Schemes C. Gavoille and M. Katz and N. Katz and C. Paul and D. Peleg ------------------------------------------------------------------- Competitive Auctions for Multiple Digital Goods Andrew V. Goldberg and Jason D. Hartline -------------------------------------------------------------------