Combinatorial optimisation considers a variety of packing problems (optimisation problems with multiple packing constraints) such as bin packing, knapsack, network flows, and subgraph packing. A multitude of general techniques have been developed to approach such packing problems, like, e.g., (integer) linear programming, local search, dynamic programming, primal-dual algorithms, iterative rounding, and relaxations. The efficiency of these techniques is well studied for special classes of packing problems under the perspective of optimising the associated objective function value and/or truthfulness, envy-freeness, etc.

This dissertation project aims at developing algorithms and complexity results for all kinds of packing problems that do not only perform in a fast and efficient way, but that additionally are able to cope with certain small changes in the underlying infrastructure and in the underlying environment. For example, for packing problems in networks such a small change in the underlying infrastructure may consist in a capacity reduction (or cost reduction) of a single arc. For the knapsack problem such a change may consist in reducing the weights of a small subset of item. In this dissertation project, the goal is to investigate the ways how general algorithmic techniques can be used to handle small changes in the input data. Primal-dual algorithms and iterative rounding procedures for combinatorial packing problems have already been studied. Complexity results and algorithms for network flow problems under uncertainties can be found in the literature as well. The performance of algorithms with respect to capacity (or cost) reductions may be measured in different ways. For example, it might be desirable to:

• maximise the objective value of the “surviving” solution, i.e., the solution that is obtained after all the variables harmed by capacity reductions have been scaled down accordingly until feasibility is reached, or
• allow for efficient re-optimisation, or
• allow for fair (and efficient) re-optimisation in the sense that the re-optimisation cost is shared in a fair manner among all variables (participants) that are harmed by the unforeseen changes in the infrastructure.

With the insights gained by this dissertation project, a long-term goal is to study and to understand the design of infrastructures that are robust against small changes in the input data and that allow for good re-optimisation. These research topics are, in particular, very relevant for network and algorithm design in railway systems.

(This dissertation project is related to the projects AL2 and AP3.)