WAOA 2005 Third Workshop on Approximation and Online Algorithms (Part of ALGO 2005) 6-7 October 2005 Hotel Tryp Bellver, Palma de Mallorca, Mallorca, Balear Islands, Spain

List of 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 $k$-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