Logo des Repositoriums
Zur Startseite
  • English
  • Deutsch
Anmelden
  1. Startseite
  2. SuUB
  3. Dissertationen
  4. Matching and packing problems – optimization under uncertainty in theory and practice
 
Zitierlink DOI
10.26092/elib/2087

Matching and packing problems – optimization under uncertainty in theory and practice

Veröffentlichungsdatum
2023-02-21
Autoren
Nölke, Lukas  
Betreuer
Megow, Nicole  
Gutachter
Krumke, Sven  
Zusammenfassung
When solving optimization problems that arise from real-world decision-making processes, uncertainty is a ubiquitous phenomenon that poses a significant obstacle. More often than not, lack of (full) knowledge about certain input parameters requires us to make decisions without knowing what their full effects will be. This thesis investigates how to algorithmically deal with such uncertainties when solving matching and packing problems.

Both matching and packing problems are well-studied and among the most fundamental problems in combinatorial optimization. In matching problems, the task is to find a set of disjoint pairs of items, a matching, while in packing problems, items need to be assigned to containers with limited capacities. Additionally, there is an optimization objective, such as minimizing the cost of the matching or maximizing the value of packed items. Both problems have numerous practical applications in which uncertainty plays an important role. It may manifest itself, for instance, in the form of unknown items that are revealed only over time.

It should come as no surprise that missing information about crucial problem parameters generally prevents us from reaching the same quality as an optimal offline solution. We consider several matching and packing problems and design algorithms that compute provably good solutions despite uncertainty in the input. Specifically, we consider the following models of uncertainty: online, recourse, and dynamic.
Schlagwörter
Matching

; 

Packing

; 

Algorithms

; 

Optimization

; 

Uncertainty
Institution
Universität Bremen  
Fachbereich
Fachbereich 03: Mathematik/Informatik (FB 03)  
Dokumenttyp
Dissertation
Lizenz
https://creativecommons.org/licenses/by/4.0/
Sprache
Englisch
Dateien
Lade...
Vorschaubild
Name

Dissertation Noelke.pdf

Size

1.83 MB

Format

Adobe PDF

Checksum

(MD5):8384575e249a2df4c7a3727f46af2589

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Datenschutzbestimmungen
  • Endnutzervereinbarung
  • Feedback schicken