Robust and Fair Algorithms for Packing Problems
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, for example 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, and so on. 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 items. Other variants can be found in for example. 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 are studied in. Complexity results and algorithms for network flow problems under uncertainties are investigated in.
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, that is 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 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.