Algo 2005
  Invited speakers

WAOA 2005 - Third Workshop on Approximation and Online Algorithms

Mallorca, Spain, October 6-7, 2005



Approximation and online algorithms are fundamental tools that deal with computationally hard problems and problems in which the input is gradually disclosed over time. Both kinds of problems have a large number of applications arising from a variety of fields. The workshop focuses on the design and analysis of algorithms for online and computationally hard problems. It also covers experimental methods used to design and analyze efficient approximation and online algorithms. WAOA 2005 will be part of ALGO 2005, which also hosts ESA, WABI, and ATMOS, and will take place 3-7 October 2005 in Mallorca, Spain.


Papers are solicited in all research areas related to approximation and online algorithms, including, but not limited to:
  • algorithmic game theory
  • approximation classes
  • coloring and partitioning
  • competitive analysis
  • computational finance
  • cuts and connectivity
  • geometric problems
  • inapproximability results
  • mechanism design
  • network design
  • packing and covering
  • paradigms
  • randomization techniques
  • real-world applications
  • scheduling problems


Proceedings will be published after the workshop takes place in the Springer series Lecture Notes in Computer Science. Instructions for authors can be found at The proceedings of WAOA 2003 and WAOA 2004 have appeared as volumes 2909 and 3351 of Lecture Notes in Computer Science, respectively.

Submission Guidelines

Authors are invited to submit an extended abstract or full paper of at most 12 pages describing original unpublished research. Simultaneous submission to other conferences with published proceedings is not permitted. The title page of the submission should include the authors' full names, addresses, fax numbers, and e-mail addresses, and an abstract summarizing the results in roughly 100-200 words; the remainder of the submission should contain a description of the main results and an explanation of their importance. Proofs omitted due to space limitations should be included in an appendix to be read by the program committee members at their discretion. Authors who wish to submit a paper must submit a Postscript or PDF file with their paper by using the electronic submission system at     (this is the preferred option)

or by sending the file by e-mail to

The submission file must be received by 23:59 (GMT) on June 10, 2005. Each accepted paper must be presented at the workshop by one of the authors.

Important Dates

Submissions: June 10, 2005
Notifications: July 18, 2005
Workshop: October 6-7, 2005
Camera Ready: November 1, 2005

Program Chairs

  • Thomas Erlebach (University of Leicester)
  • Pino Persiano (UniversitÓ di Salerno)

Program Committee

  • Evripidis Bampis (University of Evry)
  • Markus Blńser (ETH ZŘrich)
  • Thomas Erlebach (University of Leicester)
  • Klaus Jansen (Universitńt Kiel)
  • Christos Kaklamanis (University of Patras)
  • Marc van Kreveld (Utrecht University)
  • Pino Persiano (UniversitÓ di Salerno)
  • Guido Proietti (UniversitÓ di L'Aquila)
  • Kirk Pruhs (University of Pittsburgh)
  • Yuval Rabani (Technion, Haifa)
  • Adi RosÚn (Technion, Haifa)
  • Martin Skutella (Universitńt Dortmund)
  • Roberto Solis-Oba (University of Western Ontario)
  • Frits Spieksma (Katholieke Universiteit Leuven)
  • Berthold V÷cking (RWTH Aachen)
For more information please contact Thomas Erlebach or Pino Persiano.

Accepted papers

  • Sven Krumke, Willem de Paepe, Diana Poensgen, Maarten Lipmann, Alberto Marchetti-Spaccamela and Leen Stougie. On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
  • Tomßs Ebenlendr, John Noga, JirÝ Sgall and Gerhard Woeginger. A note on semi-online machine covering
  • Alessandro Ferrante, Gennaro Parlato, Francesco Sorrentino and Carmine Ventre. Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents
  • Alexander Grigoriev and Marc Uetz. Scheduling Parallel Jobs with Linear Speedup
  • Yossi Azar and Amir Epstein. The Hardness of Network Design for Unsplittable Flow with Selfish Users
  • Hadas Shachnai, Tami Tamir and Omer Yehezkely. Approximation Schemes for Packing with Item Fragmentation
  • Leah Epstein and Asaf Levin. The conference call search problem in wireless networks
  • Sven Krumke and Elisabeth Gassner. Deterministic Online Optical Call Admission Revisited
  • Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Ales Privetivy and Anand Srivastav. On the Minimum Load Coloring Problem
  • Reuven Bar-Yehuda, Ido Feldman and Dror Rawitz. Improved Approximation Algorithm for Convex Recoloring of Trees
  • David J Abraham, Peter Biro and David F Manlove. ''Almost stable'' matchings in the Roommates problem
  • Moshe Lewenstein and Zvi Gotthilf. Tighter Approximations on Greedy for Maximum Induced Matchings in Regular Graphs
  • Bodo Manthey. On Approximating Restricted Cycle Covers
  • Leah Epstein and Asaf Levin. SONET ADMs minimization with divisible paths
  • Toshihiro Fujito and Hidekazu Kurahashi. A Better-than-Greedy Algorithm for k-Set Multicover
  • Markus Blaeser and Shankar Ram Lakshminarayanan. On the Hardness and Approximate Fair Cost Allocation in Metric TSP Games
  • Adi Avidor, Ido Berokovitch and Uri Zwick. Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT
  • Stefan Heinz, Sven O. Krumke, Nicole Megow, Joerg Rambau, Andreas Tuchscherer and Tjark Vredeveld. The Online Target Date Assignment Problem
  • Kirk Pruhs, Rob van Stee and Patchrawat Uthaisombut. Speed Scaling of Tasks with Precedence Constraints
  • Xin Han, Kazuo Iwama and Guochuan Zhang. Online Removable Square Packing
  • Reuven Bar Yehuda and Jonathan Laserson. Exploiting Locality: Approximating Sorting Buffers
  • Benjamin Doerr, Tobias Friedrich, Christian Klein and Ralf Osbild. Rounding of Sequences and Matrices, with Applications
  • Ronald Koch, Ines Spenke and Martin Skutella. Approximation and Complexity of $-Splittable Flows
  • Tim Nieberg and Johann Hurink. A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
  • Danny Segev and Asaf Levin. Partial Multicuts in Trees
  • Dimitris Fotakis, Spyros Kontogiannis and Paul Spirakis. Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost