Approximation and Online Algorithms : Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Selected Papers

by Erlebach, Thomas; Persiano, Giuseppe

• ISBN13: 9783540322078
• ISBN10: 3540322078
• Format: Paperback
• Copyright: 2006-03-15
• Publisher: Springer Verlag

Summary

This book constitutes the thoroughly refereed post proceedings of the Third International Workshop on Approximation and Online Algorithms, WAOA 2005, held in Palma de Mallorca, Spain in October 2005 as part of the ALGO 2005 event. The 26 revised full papers presented were carefully reviewed and selected from 68 submissions. Topics addressed by the workshop are 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, and scheduling problems.

Table of Contents

"Almost Stable" Matchings in the Roommates Problem
David J. Abraham, Péter Biro, David F. Manlove	1	(14)
On the Minimum Load Coloring Problem
Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Aleš Privetivý, Anand Srivastav	15	(12)
Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT
Adi Avidor, Ido Berkovitch, Uri Zwick	27	(14)
The Hardness of Network Design for Unsplittable Flow with Selfish Users
Yossi Azar, Amir Epstein	41	(14)
Improved Approximation Algorithm for Convex Recoloring of Trees
Reuven Bar-Yehuda, Ido Feldman, Dror Rawitz	55	(14)
Exploiting Locality: Approximating Sorting Buffers
Reuven Bar-Yehuda, Jonathan Laserson	69	(13)
Approximate Fair Cost Allocation in Metric Traveling Salesman Games
M. Bläser, L. Shankar Ram	82	(14)
Rounding of Sequences arid Matrices, with Applications
Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild	96	(14)
A Note on Semi-online Machine Covering
Tomáš, Ebenlendr, John Noga, Jiri Sgall, Gerhard Woeginger	110	(9)
SONET ADMs Minimization with Divisible Paths
Leah Epstein, Asaf Levin	119	(14)
The Conference Call Search Problem in Wireless Networks
Leah Epstein, Asaf Levin	133	(14)
Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents
A. Ferrante, G. Parlato, F. Sorrentino, C. Ventre	147	(14)
Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost
Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis	161	(15)
A Better-Than-Greedy Algorithm for k-Set Multicover
Toshihiro Fujito, Hidekazu Kurahashi	176	(14)
Deterministic Online Optical Call Admission Revisited
Elisabeth Gassner, Sven O. Krumke	190	(13)
Scheduling Parallel Jobs with Linear Speedup
Alexander Grigoriev, Marc Uetz	203	(13)
Online Removable Square Packing
Xin Han, Kazuo Iwama, Guochuan Zhang	216	(14)
The Online Target Date Assignment Problem
S. Heinz, S.O. Krumke, N. Megow, J. Rambau, A. Tuchscherer, T. Vredeveld	230	(14)
Approximation and Complexity of k–Splittable Flows
Ronald Koch, Martin Skutella, Ines Spenke	244	(14)
On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Maarten Lipmann, Alberto Marchetti-Spaccamela, Leen Stougie	258	(12)
Tighter Approximations for Maximum Induced Matchings in Regular Graphs
Zvi Gotthilf, Moshe Lewenstein	270	(12)
On Approximating Restricted Cycle Covers
Bodo Manthey	282	(14)
A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
Tim Nieberg, Johann Hurink	296	(11)
Speed Scaling of Tasks with Precedence Constraints
Kirk Pruhs, Rob van. Stee, Patchrawat Uthaisombut	307	(13)
Partial Multicuts in Trees
Asaf Levin, Danny Segev	320	(14)
Approximation Schemes for Packing with Item Fragmentation
Hadas Shachnai, Tami Tamir, Omer Yehezkely	334	(15)
Author Index	349