Frits Spieksma

Robust Balanced Optimization Problems

We investigate the complexity and approximability of a particular family of robust optimization problems. We show that many problems within this family are NP-hard, and admit a 2-approximation algorithm that is best-possible. One interesting member of this class of problems is the robust optimization version of the balanced assignment problem; we settle the complexity of special cases of this problem, and we experimentally assess the quality of algorithms proposed for this problem. We also intend to review known results for stochastic versions of this problem. Related to this set of problems is a stochastic optimization problem occurring in kidney exchange programs. We present ongoing work that focusses on understanding the available recourse options in this problem.