# Accepted papers

in order of submission

*On the Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help
*

Thomas Jansen and Ingo Wegener

*Faster Exact Solutions for Some NP-Hard Problems
*

Limor Drori and David Peleg

*Convex Quadratic Programming Relaxations for Network Scheduling Problems
*

Martin Skutella

*The impact of knowledge on broadcasting time in radio networks
*

K. Diks, E. Kranakis, D. Krizanc and A. Pelc

*Efficient Approximation Algorithms for the Achromatic Number
*

Piotr Krysta and Krzysztof Lorys

*Augmenting an (l-1)-Vertex-Connected Multigraph to a k-Edge-Connected and l-Vertex-Connected Multigraph
*

Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki

*Motif statistics
*

Pierre Nicodeme, Bruno Salvy and Philippe Flajolet

*Off-line Temporary Tasks Assignment
*

Y. Azar and O. Regev

*Random Cayley graphs with O(log G) generators are expanders
*

Igor Pak

*On the Informational Asymmetry between Upper and Lower Bounds for Ultrametric Evolutionary Trees
*

Ting Chen and Ming-Yang Kao

*Multipacket routing on 2-D meshes and its applications to fault-tolerant routing
*

K. Iwama and E. Miyano

*Sum Multi-Coloring of Graphs
*

Amotz Bar-Noy, Magnus M. Halldorsson, Guy Kortsarz, Ravit Salman and Hadas Shachnai

*Improving Mergesort for Linked Lists
*

Salvador Roura

*Load Balancing Using Bisectors - A Tight Average-Case Analysis
*

Stefan Bischof, Thomas Schickinger and Angelika Steger

*On computing the diameter of a point set in high dimensional Eucledian space
*

Daniele V. Finocchiaro and Marco Pellegrini

*On constructing suffix arrays in external memory
*

Andreas Crauser and Paolo Ferragina

* Efficient Algorithms for Integer Programs with Two Variables per Constraint
*

Reuven Bar-Yehuda and Dror Rawitz

*Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines
*

Leah Epstein and Jiri Sgall

*Optimal binary search with two unreliable tests and minimum adptiveness
*

Ferdinando Cicalese and Daniele Mundici

*Geometric Searching over the Rationals
*

Bernard Chazelle

*Dilworth's Theorem and its application for path systems of a cycle - implementation and analysis
*

Andras Benczur, Zoltan Kiraly and Joerg Forster

*Efficient algorithms for on-line symbol ranking compression
*

G. Manzini

*On List Update and Work Function Algorithms
*

Eric Anderson, Kris Hildrum, Anna R. Karlin, April Rasala and Michael Saks

*Threshold phenomena in random lattices and efficient reduction algorithms
*

Ali Akhavi

*Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design
*

R. Ravi and F.S. Salman

*A nearly linear-time approximation scheme for the Euclidean k-median problem
*

Stavros G. Kolliopoulos and Satish Rao

*On 2-coverings and 2-packings of laminar families
*

J.Cheriyan, T.Jordan and R.Ravi

*Quartet cleaning: Improved algorithms and simulations
*

Vincent Berry, Tao Jiang, Paul Kearney, Ming Li and Todd Wareham

*IP Address Lookup Made Fast and Simple
*

Crescenzi, Dardini and Grossi

*A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications in Evolutionary Trees
*

M.Y. Kao, T.W. Lam, W.K. Sung and H.F. Ting

*Efficient Searchingfor Multi-Dimensional Data Made Simple
*

E. Nardelli, M. Talamo and P. Vocca

*On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs
*

Alexander A. Ageev

*Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices
*

Volker Heun

*Provably good and practical strategies for non-uniform data management in networks
*

F. Meyer auf der Heide, B. Voecking and M. Westermann

*On-line load Balancing in a Hierarchical Server Topology
*

Amotz Bar-Noy, Ari Freund and Seffi Naor

*Strategies for Searching with Different Access Costs
*

Eduardo Sany Laber, Ruy Milidiu and Artur Alves Pessoa

*A polyhedral algorithm for packings and designs
*

Lucia Moura

*Fast and Robust Smallest Enclosing Balls
*

Bernd Gaertner

*Resource Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems
*

Rolf H. Moehring, Andreas S. Schulz, Frederik Stork and Marc Uetz

*The 3-Server Problem in the Plane
*

W. Bein, M. Chrobak and L. Larmore

*Approximation algorithms for restoration capacity planning
*

Steven Phillips and Jeff Westbrook

*A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
*

Pavol Hell, Ron Shamir and Roded Sharan

*A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
*

Xin He, Ming-Yang Kao and Hsueh-I Lu

*An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling
*

Karen Aardal and Bram Verweij