recoverable robust optimization

Recoverable Robust Cardinality Constrained Maximization with Commitment of a Submodular Function

  • Sabine Münch
  • Sven de Vries
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more

    Recoverable Robust Knapsacks: $\GammahBcScenarios

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by … Read more