|
Third Workshop on Approximation and Online Algorithms
6-7 October 2005
Hotel Tryp Bellver, Palma de Mallorca,
Mallorca, Balear Islands, Spain
|
|
WAOA 2005 Program (click here for the full ALGO program)
THURSDAY, 6th October 2005
09:00-09:50 ALGO PLENARY INVITED TALK: Seffi Naor
09:50-10:00 short break
CHAIR: Marc van Kreveld
10:00-10:25 Yossi Azar and Amir Epstein. The Hardness of Network Design for
Unsplittable Flow with Selfish Users
10:25-10:50 Ronald Koch, Ines Spenke and Martin Skutella. Approximation and
Complexity of $k$-Splittable Flows
10:50-11:20 Break
CHAIR: Kirk Pruhs
11:20-11:45 Leah Epstein and Asaf Levin. The conference call search problem in
wireless networks
11:45-12:10 Leah Epstein and Asaf Levin. SONET ADMs minimization with divisible
paths
12:10-12:35 Sven Krumke and Elisabeth Gassner. Deterministic Online Optical
Call Admission Revisited
12:35-13:00 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
13:00-15:00 Lunch
CHAIR: Klaus Jansen
15:00-15:25 Hadas Shachnai, Tami Tamir and Omer Yehezkely. Approximation
Schemes for Packing with Item Fragmentation
15:25-15:50 Xin Han, Kazuo Iwama and Guochuan Zhang. Online Removable Square
Packing
15:50-16:15 Stefan Heinz, Sven O. Krumke, Nicole Megow, Joerg Rambau, Andreas
Tuchscherer and Tjark Vredeveld. The Online Target Date Assignment
Problem
16:15-16:45 Break
Chair: Leen Stougie
16:45-17:10 Moshe Lewenstein and Zvi Gotthilf. Tighter Approximations on Greedy
for Maximum Induced Matchings in Regular Graphs
17:10-17:35 David J Abraham, Peter Biro and David F Manlove. "Almost stable"
matchings in the Roommates problem
17:35-18:00 Tim Nieberg and Johann Hurink. A PTAS for the Minimum Dominating
Set Problem in Unit Disk Graphs
FRIDAY, 7th October 2005
CHAIR: Rob van Stee
09:10-09:35 Reuven Bar-Yehuda, Ido Feldman and Dror Rawitz. Improved
Approximation Algorithm for Convex Recoloring of Trees
09:35-10:00 Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Ales Privetivy and
Anand Srivastav. On the Minimum Load Coloring Problem
10:00-10:25 Danny Segev and Asaf Levin. Partial Multicuts in Trees
10:25-10:50 Bodo Manthey. On Approximating Restricted Cycle Covers
10:50-11:20 Break
CHAIR: Berthold Vöcking
11:20-11:45 Kirk Pruhs, Rob van Stee and Patchrawat Uthaisombut. Speed Scaling
of Tasks with Precedence Constraints
11:45-12:10 Alexander Grigoriev and Marc Uetz. Scheduling Parallel Jobs with
Linear Speedup
12:10-12:35 Tomás Ebenlendr, John Noga, Jirí Sgall and Gerhard Woeginger. A
note on semi-online machine covering
12:35-13:00 Reuven Bar Yehuda and Jonathan Laserson. Exploiting Locality:
Approximating Sorting Buffers
13:00-15:00 Lunch
CHAIR: Sven Krumke
15:00-15:25 Markus Blaeser and Shankar Ram Lakshminarayanan. On the Hardness
and Approximate Fair Cost Allocation in Metric TSP Games
15:25-15:50 Dimitris Fotakis, Spyros Kontogiannis and Paul Spirakis. Symmetry
in Network Congestion Games: Pure Equilibria and Anarchy Cost
15:50-16:15 Alessandro Ferrante, Gennaro Parlato, Francesco Sorrentino and
Carmine Ventre. Improvements for Truthful Mechanisms with
Verifiable One-Parameter Selfish Agents
16:15-16:45 Break
CHAIR: Thomas Erlebach
16:45-17:10 Benjamin Doerr, Tobias Friedrich, Christian Klein and Ralf Osbild.
Rounding of Sequences and Matrices, with Applications
17:10-17:35 Toshihiro Fujito and Hidekazu Kurahashi. A Better-than-Greedy
Algorithm for k-Set Multicover
17:35-18:00 Adi Avidor, Ido Berokovitch and Uri Zwick. Improved Approximation
Algorithms for MAX NAE-SAT and MAX SAT