## Having a Plan B for Robust Optimization

- We continue in this paper the study of k-adaptable robust solutions for combinatorial optimization problems with bounded uncertainty sets. In this concept not a single solution needs to be chosen to hedge against the uncertainty. Instead one is allowed to choose a set of k different solutions from which one can be chosen after the uncertain scenario has been revealed. We first show how the problem can be decomposed into polynomially many subproblems if k is fixed. In the remaining part of the paper we consider the special case where k=2, i.e., one is allowed to choose two different solutions to hedge against the uncertainty. We decompose this problem into so called coordination problems. The study of these coordination problems turns out to be interesting on its own. We prove positive results for the unconstrained combinatorial optimization problem, the matroid maximization problem, the selection problem, and the shortest path problem on series parallel graphs. The shortest path problem on general graphs turns out to be NP-complete. Further, we present for minimization problems how to transform approximation algorithms for the coordination problem to approximation algorithms for the original problem. We study the knapsack problem to show that this relation does not hold for maximization problems in general. We present a PTAS for the corresponding coordination problem and prove that the 2-adaptable knapsack problem is not at all approximable.

Author: | André Chassein |
---|---|

URN (permanent link): | urn:nbn:de:hbz:386-kluedo-50970 |

Document Type: | Preprint |

Language of publication: | English |

Publication Date: | 2017/12/11 |

Year of Publication: | 2017 |

Publishing Institute: | Technische Universität Kaiserslautern |

Date of the Publication (Server): | 2017/12/12 |

Number of page: | 43 |

Faculties / Organisational entities: | Fachbereich Mathematik |

DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |

MSC-Classification (mathematics): | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C47 Minimax problems [See also 49K35] | |

Licence (German): | Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0) |