[Mittagsseminar TI] Fwd: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

-------- Original Message --------
Subject: 	[i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: 	Tue, 18 Feb 2014 13:48:43 +0100
From: 	Robert Lion Gottwald <robert.gottwald@fu-berlin.de>
To: 	i-studi@inf.fu-berlin.de, i-profs@inf.fu-berlin.de,
i-wimis@inf.fu-berlin.de



Sehr geehrte Damen und Herren,
hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit dem
Titel "Approximation Algorithms for Interval Scheduling Problems with Given
Machines" ein.

Die Verteidigung findet am 21.02 um 11.00 Uhr s.t. im Raum SR049 Takustr. 9
statt. Der Erstgutachter ist Prof. Dr. Wolfgang Mulzer und der
Zweitgutachter
ist Dr. habil. Panos Giannopoulus.

Mit freundlichen Grüßen,
Robert Lion Gottwald


Abstract:

Most interesting discrete optimization problems are NP-hard and thus the
existence of algorithms that find optimal solutions efficiently is very
unlikely for these problems. One approach to encounter this is to design
efficient algorithms that find approximate solutions. In this thesis two NP-
hard interval scheduling problems are studied. In both the goal is to
schedule
a set of intervals on given machines such that intervals scheduled on
the same
machine do not overlap. Additionally, the machines have a capacity
constraint
in one of the variants, while in the other one an interval can be restricted
to a subset of the machines. They fall into a class of problems called
/separable assignment problems/, for which a framework to obtain
approximation
algorithms, whose guarantees depend on the problem for a single machine,
exists.
On the basis of this framework I will describe a local search approximation
algorithm and one using linear programming with randomized rounding for both
problems.

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature