Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 14, 2011

Humboldt-Universität zu Berlin

Rudower Chaussee 26
12489 Berlin
room 0'310

Lecture - 14:15

Susanne Albers, HU Berlin

Energy-Efficient Algorithms for Variable-Speed Processors

Modern microprocessors manufactured by Intel and AMD allow the frequency/speed to be set dynamically. High speeds imply high performance but also high energy consumption. The goal of dynamic speed scaling is to use the full speed/frequency spectrum of a processor so as to minimize energy consumption, while still providing a desired service. We study a classical speed-scaling problem where a set of jobs, each specified by a release time, a deadline and a processing volume, has be executed on a variable-speed processor. Prior work focused mostly on settings with a single processor. In this talk we investigate two generalized scenarios. (1) A set of parallel processors is available. We show that the offline problem is polynomially solving using maximum-flow computation. We also devise two online algorithms. (2) A processor is equipped with an additional sleep state. We show that the offline problem is NP-hard and develop improved constant factor approximation algorithms.
This is joint work with Antonios Antoniadis and Gero Greiner, published in SPAA'11 and SODA'12.

Colloquium - 16:00

Louis Theran, FU Berlin

Generic periodic rigidity

A periodic framework is a planar structure, periodic with respect to a lattice, made of fixed length bars connected by joints with full rotational freedom. The allowed motions preserve periodicity and the lengths and connectivity of the bars. When all the allowed motions are isometries, a framework is rigid. Periodic frameworks generalize the widely studied (finite) "bar-joint" model and come up in engineering and crystallography applications, among others.

For "generic" periodic frameworks, rigidity has an efficiently checkable combinatorial characterization, which I'll describe in this talk.

Letzte Aktualisierung: 04.11.2011