#
Monday Lecture and Colloquium

**Monday, May 19, 2014**

Technische Universität Berlin

Fakultät II, Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

### Rolf Niedermeier -
Technische Universität Berlin

### On (Combinatorial) Anonymization

*Abstract:*

We review our recent work on analyzing the computational
complexity (particularly, parameterized complexity)
of combinatorial data anonymization, mainly
discussing degree-based network anonymization.
Roughly speaking, an object is called k-anonymous
if there are at least k-1 other objects in the data
that "look the same". In case of graphs, a vertex is
called k-anonymous if there are at least k-1 other
vertices having the same degree.
The goal to make a graph k-anonymous (that is,
all its vertices shall be k-anonymous) leads to
a number of algorithmic graph modification problems that
are mostly NP-hard.

This talk is based on joint work with Robert Bredereck,
Vincent Froese, Sepp Hartung, André Nichterlein, Geevarghese Philip,
Ondrej Suchý, Nimrod Talmon, and Gerhard Woeginger.

** Colloquium - 16:00**

### Roman Rischke -
Technische Universität Berlin

### Two-Stage Scheduling on Unrelated Machines

*Abstract:*

We consider a natural model for two-stage scheduling on unrelated machines in which reserving a time unit for processing jobs incurs some cost. This cost depends on the time at which the reservation is made: a priori decisions, based only on distributional information, are much cheaper than on-demand decisions made when the actual scheduling scenario is known. Such a model captures for example the resource provisioning problem that users of cloud computing services face.

Our main contribution is an LP-rounding based (8+ε)-approximation algorithm for both the stochastic and the robust version of this problem with a polynomial number of scenarios. The key ingredient is a separation of jobs and time slots to be considered in either the first or the second stage only. At the expense of another ε our result holds for any arbitrary scenario distribution given by means of a black-box in the two-stage stochastic problem.

This is joint work with Lin Chen, Nicole Megow, and Leen Stougie.

Letzte Aktualisierung:
09.05.2014