• Deutsch
    • English
  • English 
    • Deutsch
    • English
  • Login
Item View 
  •   Home
  • Naturwissenschaften, Mathematik und Informatik
  • Fakultät für Mathematik und Informatik (inkl. GAUSS)
  • Item View
  •   Home
  • Naturwissenschaften, Mathematik und Informatik
  • Fakultät für Mathematik und Informatik (inkl. GAUSS)
  • Item View
JavaScript is disabled for your browser. Some features of this site may not work without it.

Randomized Approximation and Online Algorithms for Assignment Problems

by Marco Bender
Doctoral thesis
Date of Examination:2015-04-23
Date of issue:2015-06-10
Advisor:Prof. Dr. Stephan Westphal
Referee:Prof. Dr. Stephan Westphal
Referee:Prof. Dr. Tjark Vredeveld
Referee:Prof. Dr. Anita Schöbel
crossref-logoPersistent Address: http://dx.doi.org/10.53846/goediss-5126

 

 

Files in this item

Name:diss.pdf
Size:977.Kb
Format:PDF
Description:Dissertation
ViewOpen

The following license files are associated with this item:


Abstract

English

In 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 paths.
Keywords: Combinatorial Optimization; Approximation Algorithms; Generalized Assignment Problem; Online Optimization; Competitive Analysis
 

Statistik

Publish here

Browse

All of eDissFaculties & ProgramsIssue DateAuthorAdvisor & RefereeAdvisorRefereeTitlesTypeThis FacultyIssue DateAuthorAdvisor & RefereeAdvisorRefereeTitlesType

Help & Info

Publishing on eDissPDF GuideTerms of ContractFAQ

Contact Us | Impressum | Cookie Consents | Data Protection Information
eDiss Office - SUB Göttingen (Central Library)
Platz der Göttinger Sieben 1
Mo - Fr 10:00 – 12:00 h


Tel.: +49 (0)551 39-27809 (general inquiries)
Tel.: +49 (0)551 39-28655 (open access/parallel publications)
ediss_AT_sub.uni-goettingen.de
[Please replace "_AT_" with the "@" sign when using our email adresses.]
Göttingen State and University Library | Göttingen University
Medicine Library (Doctoral candidates of medicine only)
Robert-Koch-Str. 40
Mon – Fri 8:00 – 24:00 h
Sat - Sun 8:00 – 22:00 h
Holidays 10:00 – 20:00 h
Tel.: +49 551 39-8395 (general inquiries)
Tel.: +49 (0)551 39-28655 (open access/parallel publications)
bbmed_AT_sub.uni-goettingen.de
[Please replace "_AT_" with the "@" sign when using our email adresses.]