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

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

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

15:50-16:15 Stefan Heinz, Sven O. Krumke, Nicole Megow, Joerg Rambau, Andreas
	    Tuchscherer and Tjark Vredeveld. The Online Target Date Assignment

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