## Robust Multicovers: Algorithms and Complexity

- The great interest in robust covering problems is manifold, especially due to the plenitude of real world applications and the additional incorporation of uncertainties which are inherent in many practical issues. In this thesis, for a fixed positive integer \(q\), we introduce and elaborate on a new robust covering problem, called Robust Min-\(q\)-Multiset-Multicover, and related problems. The common idea of these problems is, given a collection of subsets of a ground set, to decide on the frequency of choosing each subset so as to satisfy the uncertain demand of each overall occurring element. Yet, in contrast to general covering problems, the subsets may only cover at most \(q\) of their elements. Varying the properties of the occurring elements leads to a selection of four interesting robust covering problems which are investigated. We extensively analyze the complexity of the arising problems, also for various restrictions to particular classes of uncertainty sets. For a given problem, we either provide a polynomial time algorithm or show that, unless \(\text{P}=\text{NP}\), such an algorithm cannot exist. Furthermore, in the majority of cases, we even give evidence that a polynomial time approximation scheme is most likely not possible for the hard problem variants. Moreover, we aim for approximations and approximation algorithms for these hard variants, where we focus on Robust Min-\(q\)-Multiset-Multicover. For a wide class of uncertainty sets, we present the first known polynomial time approximation algorithm for Robust Min-\(q\)-Multiset-Multicover having a provable worst-case performance guarantee.

Author: | Eva SchmidtORCiD |
---|---|

URN: | urn:nbn:de:hbz:386-kluedo-67020 |

ISBN: | 978-3-8439-4939-2 |

Publisher: | Verlag Dr. Hut |

Place of publication: | München |

Advisor: | Sven Oliver Krumke |

Document Type: | Doctoral Thesis |

Language of publication: | English |

Publication Date: | 2021/12/21 |

Year of Publication: | 2021 |

Publishing Institute: | Technische Universität Kaiserslautern |

Granting Institute: | Technische Universität Kaiserslautern |

Acceptance Date of the Thesis: | 2021/09/03 |

Date of the Publication (Server): | 2021/12/22 |

Tag: | Constraint Generation; Multiset Multicover; Robust Optimization |

Number of page: | XI, 222 |

Source: | https://www.dr.hut-verlag.de/9783843949392.html |

Faculties / Organisational entities: | Fachbereich Mathematik |

CCS-Classification (computer science): | G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.m Miscellaneous |

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

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

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C17 Robustness in mathematical programming | |

Licence (German): | Zweitveröffentlichung |