Algo 2005
  Invited speakers

13th Annual European Symposium on Algorithms - ESA 2005

Mallorca, Spain, October 3-6, 2005


The Symposium covers research in the use, design and analysis of efficient algorithms and data structures in computer science, discrete applied mathematics, operations research and mathematical programming. The Symposium has two tracks, which deal respectively with:

  • the design and mathematical analysis of algorithms (the ''Design and Analysis'' track)
  • real-world applications, engineering and experimental analysis of algorithms (the ''Engineering and Applications'' track).

ESA 2005 is sponsored by EATCS (the European Association for Theoretical Computer Science) and organized in the context of ALGO 2005. For updated information see the ESA 2005 web site.


Papers presenting original research in all area of algorithmic research are sought, including but not limited to algorithmic aspects of networks, approximation and on-line algorithms, computational biology, computational geometry, computational finance and algorithmic game theory, data structures, database and information retrieval, external memory algorithms, graph algorithms, graph drawing, machine learning, mobile computing, pattern matching and data compression, quantum computing, randomized algorithms. The algorithms may be sequential, distributed or parallel.

Submissions are especially encouraged in the area of mathematical programming and operations research, including combinatorial optimization, integer programming, polyhedral combinatorics, and semidefine programming.


Authors are invited to submit an extended abstract or full paper of at most 12 pages. The paper should contain a succinct statement of the issues and of their motivation, a summary of the main results, and a brief explanation of their significance, accessible to non-specialist readers. Proofs omitted due to space constraints must be put into an appendix to be read by the program committee members at their discretion. Electronic submission is *highly recommended*. Please use the following links:

In case of problems with access to internet, it is possible to submit 6 copies of the paper to the program committee chair:

Design and Analysis Track
Stefano Leonardi
Dipartimento di Informatica e Sistemistica
Universita' di Roma ``La Sapienza''
Via Salaria 113
00198 Roma
  Engineering and Applications Track
Gerth Stølting Brodal
University of Aarhus
Department of Computer Science
IT-parken, Aabogade 34
8200 Aarhus N

Hard copy submissions must be received by April 12 or postmarked no later than April 5 and sent by airmail to be considered. Authors are expected to present their accepted papers at the conference.

Simultaneous submission

Simultaneous submission to other conferences with published proceedings, or to both tracks of ESA 2005, is not permitted. A paper submitted to one track of ESA 2005 may be switched to the other track if, in the opinion of the PC chairs, the paper is better suited to the other track.

Best student paper award

EATCS sponsors an award for the best student paper at ESA 2005. All of a paper's authors must be students for the paper to be considered for this award. Please indicate student paper on the front page of the submission if all authors are students.


Accepted papers will be published in the Springer series Lecture Notes in Computer Science. Previous proceedings of ESA 2002 in Rome, 2003 in Budapest, and 2004 in Bergen appeared as LNCS 2461, 2832, and 3221. Accepted contributed papers will receive an allotment of 12 pages in the proceedings.

Program committee

Design and Analysis Track

  • Dimitris Achlioptas (Microsoft Research)
  • Michael Bender (Stony Brook)
  • Alberto Caprara (Bologna)
  • Friedrich Eisenbrand (Saarbrüucken)
  • Luisa Gargano (Salerno)
  • Andrew Goldberg (Microsoft Research)
  • Haim Kaplan (Tel-Aviv)
  • Jochen Koenemann (Waterloo)
  • Stefano Leonardi (Chair) (Rome)
  • Kirk Pruhs (Pittsburgh)
  • Edgar Ramos (Urbana-Champaign)
  • Adi Rosen (Technion)
  • Maria Serna (Barcelona)
  • Christian Sohler (Paderborn)
  • Emo Welzl (ETH Zurich)
  • Berthold Vöcking (RWTH Aachen)

Engineering and Applications Track

  • Jon Bentley (Avaya)
  • Gerth Stølting Brodal (Chair) (Aarhus)
  • Hervé Brönnimann (Brooklyn Poly)
  • Adam L. Buchsbaum (AT&T)
  • Riko Jacob (ETH Zurich)
  • Richard Ladner (Washington)
  • Sotiris Nikoletseas (Patras)
  • Jordi Petit (Barcelona)
  • Bettina Speckmann (Eindhoven)
  • Subhash Suri (Santa Barbara)
  • Sivan Toledo (Tel-Aviv)

Accepted papers

Design and Analysis Track

* A 2-Approximation Algorithm for Sorting by Prefix Reversals  Johannes Fischer and Simon W. Ginzinger

* Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs  Andreas Björklund

* An algorithm for the SAT problem for formulae of linear length  Magnus Wahlström

* A Loopfree Gray Code for Minimal Signed-Binary Representations  Gurmeet Singh Manku and Joe Sawada

* Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs  Sergio Cabello and Bojan Mohar

* Improved Approximation Algorithms for Metric Max TSP  Zhi-Zhong Chen and Takayuki Nagoya

* A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time (Extended Abstract)  Robert R. Benkoczi AND Binay. K. Bhattacharya

* Computing common intervals of K permutations, with applications to modular decomposition of graphs  Anne Bergeron, Cedric Chauve, Fabien de Montgolfier, Mathieu Raffinot

* Complexity of Robust Approximate Zeros  Vikram Sharma and Zilin Du and Chee K. Yap

* Efficient Approximation Schemes for Geometric Problems?  Dániel Marx

* Optimal Integer Alphabetic Trees in Linear Time  T. C. Hu and Lawrence L. Larmore and J. David Morgenthaler

* Roll cutting in the curtain industry, or: A well-solvable allocation problem  A Alfieri, SL van de Velde, GJ Woeginger

* An approximation algorithm for the minimum latency set cover problem  Refael Hassin and Asaf Levin

* Online Bin Packing with Cardinality Constraints  Leah Epstein

* Using Fractional Primal-Dual to Schedule Split Intervals with Demands  Reuven Bar-Yehuda and Dror Rawitz

* Making Chord Robust to Byzantine Attacks  Amos Fiat and Jared Saia and Maxwell Young

* On degree constrained shortest paths  Samir Khuller and Kwangil Lee and Mark Shayman

* Online Routing in Faulty Meshes with Sub-Linear Comparative Time and Traffic Ratio  Stefan Rührup and Christian Schindelhauer

* Small stretch spanners on dynamic graphs  Giorgio Ausiello and Paolo G. Franciosa and Giuseppe F. Italiano

* 5-Regular Multi-Graphs are 3-Colorable with Independent of their Size Positive Probability  J. Diaz and G. Grammatikopoulos and A.C. Kaporis and L.M. Kirousis and X. Perez and D.G. Sotiropoulos

* On the price of anarchy and stability of correlated equilibria of linear congestion games  George Christodoulou and Elias Koutsoupias

* Packet Routing and Information Gathering in Lines, Rings and Trees  Yossi Azar and Rafi Zachut

* Low Degree Connectivity in Ad-hoc Networks  Ludek Kucera

* Bucket Game with Applications to Set Multicover and Dynamic Page Migration  Marcin Bienkowski and Jaroslaw Byrka

* Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs  Andre Berger, Artur Czumaj, Michelangelo Grigni, and Hairong Zhao

* Online View Maintenance under a Response-Time Constraint  Kamesh Munagala and Jun Yang and Hai Yu

* The Complexity of Games on Highly Regular Graphs (Extended Abstract)  Konstantinos Daskalakis and Christos H. Papadimitriou

* An algorithm for node-capacitated ring routing  Andras Frank and Zoltan Kiraly and Balazs Kotnyek

* New tools and simpler algorithms for branchwidth  C.Paul and J.A.Telle

* Efficient $-Oriented Range Searching with DOP-Trees  Mark de Berg and Herman Haverkort and Micha Streppel

* Fast monotone 3-approximation algorithm for scheduling related machines  Annamaria Kovacs

* Minimal interval completions  Pinar Heggernes and Karol Suchan and Ioan Todinca and Yngve Villanger

* Linear-Time Enumeration of Isolated Cliques  Hiro Ito, Kazuo Iwama, and Tsuyoshi Osumi

* Jitter Regulation for Multiple Streams  David Hay and Gabriel Scalosub

* Predecessor Queries in Constant Time?  Marek Karpinski and Yakov Nekrich

* Approximating the 2-Interval Pattern problem  Maxime Crochemore and Danny Hermelin and Gad M. Landau and Stephane Vialette

* Shortest Paths in Matrix Multiplication Time  Piotr Sankowski

* Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
 Frederic Dorn and Eelko Penninkx and Hans L. Bodlaender and Fedor V. Fomin

* Min Sum Clustering with Penalties  Refael Hassin and Einat Or

* An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees  Ferdinando Cicalese and Eduardo Sany Laber

* Matching Point Sets with respect to the Earth Mover's Distance  Sergio Cabello and Panos Giannopoulos and Christian Knauer and Günter Rote

* Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delay  A.V.Fishkin and K.Jansen and S.Sevastianov and R.Sitters

* Greedy Routing in Tree-Decomposed Graphs  Pierre Fraigniaud

* Fairness-Free Periodic Scheduling  Jiri Sgall and Hadas Shachnai and Tami Tamir

* Exploring an unknown graph efficiently  Rudolf Fleischer and Gerhard Trippen

* Online Primal-Dual Algorithms for Covering and Packing Problems  Niv Buchbinder and Joseph (Seffi) Naor

* Unbalanced Graph Cuts  Ara Hayrapetyan and David Kempe and Martin Pal and Zoya Svitkina

* Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack  Hassene Aissi and Cristina Bazgan and Daniel Vanderpooten

* Bootstrapping a Hop-optimal Network in the Weak Sensor Model  Martin Farach-Colton and Rohan Fernandes and Miguel A. Mosteiro

* Workload-Optimal Histograms on Streams  S. Muthukrishnan and M. Strauss and X. Zheng

* Finding Frequent Patterns in a String in Sublinear Time  Petra Berenbrink and Funda Ergun and Tom Friedetzky

* Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information  Yigal Bejerano, Joseph (Seffi) Naor, and Alexander Sprintson

* Cache-oblivious comparison-based algorithms on multisets  Arash Farzan and Paolo Ferragina and Gianni Franceschini and J. Ian Munro

* Geometric clustering to minimize the sum of cluster sizes  Vittorio Bilo and Ioannis Caragiannis and Christos Kaklamanis and Panagiotis Kanellopoulos

* Optimizing a 2D Function Satisfying Unimodality Properties  Erik D. Demaine and Stefan Langerman

Engineering and Applications Track

* Experimental study of geometric t-spanners
 Mohammad Farshi and Joachim Gudmundsson

* I/O-Efficient Construction of Constrained Delaunay Triangulations
 Pankaj K. Agarwal and Lars Arge and Ke Yi

* Delineating boundaries for imprecise regions
 Iris Reinbacher and Marc Benkert and Marc van Kreveld and  Joseph S.B. Mitchell and Alexander Wolff

* Generating Realistic Terrains with Higher-Order Delaunay  Triangulations
 Thierry de Kok and Marc van Kreveld and Maarten Loffler

* Space Efficient Algorithms for the Burrows-Wheeler Backtransformation
 Ulrich Lauther and Tamas Lukovszki

* Stxxl: Standard Template Library for XXL Data Sets
 Roman Dementiev and Lutz Kettner and Peter Sanders

* Treewidth Lower Bounds with Brambles
 Hans L. Bodlaender and Alexander Grigoriev and Arie M. C. A. Koster

* An Experimental Study of Algorithms for Fully Dynamic Transitive Closure
 Ioannis Krommidas and Christos Zaroliagis

* Allocating memory in a lock-free manner
 Anders Gidenstam and Marina Papatriantafilou and Philippas Tsigas

* Engineering Planar Separator Algorithms  Martin Holzer and Grigorios Prasinos and Frank Schulz and Dorothea Wagner and Christos Zaroliagis

* Convex Hull and Voronoi Diagram of Additively Weighted Points
 Christophe Delage and Jean-Daniel Boissonnat

* A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem
 Alain Faye and Frédéric Roupin

* Heuristic improvements for computing maximum multicommodity flow and minimum multicut
 Garima Batra and Naveen Garg and Garima Gupta

* Oblivious vs. Distribution-based Sorting: An Experimental Evaluation
 Geeta Chaudhry and Thomas H. Cormen

* Computing Equilibrium Prices: Does Theory Meet Practice?
 Bruno Codenotti and Benton McCune and Rajiv Raman and Kasturi Varadarajan

* Highway Hierarchies Hasten Exact Shortest Path Queries
 Peter Sanders and Dominik Schultes

* EXACUS---Efficient and Exact Algorithms for Curves and Surfaces
 Eric Berberich and Arno Eigenwillig and Michael Hemmer and Susan Hert and Lutz Kettner and Kurt Mehlhorn and Joachim Reichel and

* Online Occlusion Culling
 Gereon Frahling and Jens Krokowski

* Relax-and-cut for capacitated network design
 Georg Kliewer and Larissa Timajev

* Negative Cycle Detection
 Wong Chi Him and Tam Yiu Cheong

Important dates

  • Submission deadline: April 12, 2005
  • Notification to authors: June 7, 2005
  • Symposium: October 3-6, 2005
  • Solar Eclipse: October 3, 2005

Related conferences

  • 24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005)