Monday, May 19, 2014
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
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
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.