Group Seminar
"Algorithms and Complexity"
Summer term 2010
Junior-Prof. Dr. Robert Elsässer
Seminars are on Tuesday from 11:00-13:00 in Building 051, Room 00 006.
21.04.2010
Randomisiertes Routing in geometrischen Zufallsnetzwerken
Bente Luth"It's a small world!" fand bereits 1967 Stanley Milgram durch die Studie sozialer Netzwerke heraus. Diese Beobachtungen wurden später mathematisch formuliert. Im Jahr 2000 hat dann Jon Kleinberg diese Netzwerke als 2-dimensionales Gitter algorithmisch analysiert, sowie obere und untere Schranken für die Übertragungszeit einer Nachricht zu einem unbekannten Ziel gezeigt.
In der Diplomarbeit wurden diese Ergebnisse aufgegriffen. Für ein i-dimensionales Zufallsnetzwerk wurde gezeigt, dass es eine obere Schranke in logarithmischer Zeit gibt. Außerdem wurden untere Schranken gefunden.
The talk take place in building 079-00-019 at 10:00 (s.t.)
22.04.2010
Batch Scheduling with Interval Compatibilities
Tim NonnerBatch scheduling deals with situations where a given set of jobs needs to be partitioned into batches of compatible jobs. The compatibility of two jobs if often determined by a single one-dimensional parameter with respect to which each job has a tolerance described by an interval. This parameter might, for example, be temporal availability or a required temperature. On the other hand, it is natural to assume that there is a capacity constraint that limits the size of each batch.
We discuss several greedy and dynamic programming techniques from literature to solve batch scheduling problems with interval compatibility and capacity constraints, and we also point out their limits. Finally, we present a novel dynamic programming technique that allows us to deal with such problems in a general way. We demonstrate the power of this technique by applying it to the max-batching problem, where each job has a weight, and the cost of a batch is the maximum weight of any job in the batch. This yields a polynomial time approximation scheme for max-batching with interval compatibility and capacity constraints.
The talk take place in building 106-04-007 at 09:00 (s.t.)