[home] - [up]


Lectures and Colloquia during the semester



June 16, 2003

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Guochuan Zhang -Universität Kiel

Scheduling Parallel Jobs on Networks

Abstract: We consider a parallel computer system with an interconnection topology, such as PRAM, Lines and Meshes. Several processors can execute a job simultaneously if they are connected in the underlying network. A parallel job requires a fixed number of processors or a specified subsystem of a certain size for its execution at a time. Our goal is to assign the parallel jobs to the processors so that the makespan is minimized or the throughput is maximized.

In many cases parallel job scheduling is related to rectangle packing. Steinberg [SIAM J Computing 26, 401-409, 1997] gave a sufficient condition to determine if a number of rectangles can be packed into a rectangular bin. We make a further extension of his theorem and apply it to several parallel job scheduling problems. We either improve the previous results or obtain some new results.

This talk is based on joint papers with K. Jansen and with D. Ye.


Colloquium - 16:00

Pawel Zylinski -University of Gdansk

Vertex cover and connected guard set

Abstract: One of a family of guard problem is the cooperative guard problem, i.e., one want to determine the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon provided that the visibility graph of the set of guards is connected. The guard is a stationary point who can see any point that can be connected to it with a line segment within the polygon.

Herein we investigate this problem for polygons, polyhedral terrains and tetrahedralizable polyhedras: we introduce the idea of a diagonal graph, and we show that a vertex cover of a diagonal graph is a cooperative vertex guard set. Also some new bounds for polyhedral terrains and tetrahedralizable polyhedras are presented.


[home] - [up] - [top]