Monday, November 14, 2011
Humboldt-Universität zu Berlin
***NEW LOCATION***
Erwin-Schrödinger-Zentrum
Rudower Chaussee 26
12489 Berlin
room 0'310
Lecture - 14:15
Abstract:
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
Abstract:
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.