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