


Online BinColoring
Sven Oliver Krumke and Willem de Paepe and Joerg Rambau and Leen Stougie

Fast Pricing of European Asian Options with Provable Accuracy: Singlestock
and Basket Options
Karhan Akcoglu and MingYang 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 kServer 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 EbbersBaumann and Rolf Klein and Elmar Langetepe and Andrzej Lingas

Algorithms for Efficient Filtering in ContentBased 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 MinimumTime Broadcast under the VertexDisjoint
Paths Mode
Pierre Fraigniaud

Online and Offline distance constrained labeling of disk graphs
Jiri Fiala and Aleksei V. Fishkin and Fedor V. Fomin

Smallest ColorSpanning 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)edgecoloring 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 2approximation algorithm for the multivehicle scheduling problem on a path
with release and handling times
Y. Karuno and H. Nagamochi

Round Robin is Optimal for FaultTolerant 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
