Monday, November 14, 2011
Humboldt-Universität zu Berlin
Rudower Chaussee 26
Lecture - 14:15
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
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.