Show simple item record

Randomized Approximation and Online Algorithms for Assignment Problems

dc.contributor.advisorWestphal, Stephan Prof. Dr.
dc.contributor.authorBender, Marco
dc.titleRandomized Approximation and Online Algorithms for Assignment Problemsde
dc.contributor.refereeWestphal, Stephan Prof. Dr.
dc.description.abstractengIn this thesis, we consider several combinatorial optimization problems which feature assignment decisions. The first part deals with variants of the generalized assignment problem. We study an extension with additional minimum quantity constraints, and a generalization where the hard capacity constraints are relaxed by adding a convex summand to the objective function. Furthermore, we analyze a version of the separable assignment problem where it is allowed to assign items to multiple bins. For all these problems, we present results on their computational complexity and provide approximation algorithms that use randomized rounding based on configuration integer programming formulations. In the second part, we study an online version of the interval scheduling problem, where an upper bound on the number of failing intervals is known in advance, from the viewpoint of competitive analysis. A similar online setting is given in the Canadian traveler problem, an online variant of the shortest-path problem. For this problem we present a randomized online algorithm and prove that it is best-possible on node-disjoint
dc.contributor.coRefereeVredeveld, Tjark Prof. Dr.
dc.contributor.thirdRefereeSchöbel, Anita Prof. Dr.
dc.subject.engCombinatorial Optimizationde
dc.subject.engApproximation Algorithmsde
dc.subject.engGeneralized Assignment Problemde
dc.subject.engOnline Optimizationde
dc.subject.engCompetitive Analysisde
dc.affiliation.instituteFakultät für Mathematik und Informatikde
dc.subject.gokfullMathematics (PPN61756535X)de

Files in this item


This item appears in the following Collection(s)

Show simple item record