Program

?Opening of the school (photo)

Kazuo Iwama ( Kyoto University )

Title: Online algorithms for server-location and resource-packing problems

Abstract: There are many situations where we need to make a choice without perfect information. For example, suppose that you received a request of package collection from some place A and you have three vehicles X, Y and Z now staying near A (but each in a quite different place). Which one should you order to go to A to collect the package? If you know that there will soon be another request near X, then X should not move. Unfortunately, of course, you do not have such information about the future. Another similar situation occurs when you pick a piece in a mahjong game; whether you should keep it or not is a difficult problem just because of the same reason. This kind of problems (called online problems) and studies on algorithms for them (online algorithms) have been increasingly popular in the last two decades. In the lecture, we learn basic ideas for design and analysis of online algorithms using server-location and resource-packing problems.

Workshop

Session 1:

Kazuo Iwama: Approximation on vertex cover

Hong Zhu: Fully truthful mechanisms

Session 2:

Min Xu: Forwarding indices of folded n-cubes

Yongqiang Shi: Generalized variable-sized bin packing

Ling Gai: Common deadline lazy bureaucrat scheduling

János Csirik ( University of Szeged )

Title: An introduction and some open problems of bin packing

Title: Scheduling for parallel and grid computing

Klaus Jansen ( University of Kiel )

Title: Approximation algorithms for scheduling problems with precedence constraints

Abstract:
1. Introduction (problem definitions, complexity, inapproximability)
2. Basic techniques (list scheduling, linear programming relaxations)
3. Scheduling with communication delays (algorithm by Hanen and Munier)
4. Scheduling malleable tasks (algorithm by Lepere, Trystram and Woeginger)