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:
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:
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 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.
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