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

Abstract

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.