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, 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

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

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