ISBN 9783843957946

978-3-8439-5794-6, Reihe Mathematik

Nils Hausbrandt
Parametric Matroid Interdiction

231 Seiten, Dissertation Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau (2026), Hardcover, A5

Zusammenfassung / Abstract

This thesis combines three important areas of research in mathematical programming: matroid theory, parametric optimization, and the concept of interdiction in optimization problems. In a matroid interdiction problem, the goal is to remove a subset of a given cardinality from the matroid's ground set that maximizes the weight of a minimum weight basis. In this thesis, we examine the multi-parametric generalization of this problem, where every weight is given by a linear function depending on a parameter vector. For every parameter vector, we are interested in an optimal interdiction strategy and the weight of an optimally interdicted basis. We investigate several variants of the problem depending on the interdiction costs, the interdiction budget, and the number of parameters. For all variants obtained, a detailed analysis, including the description of the structure of an optimal solution, the determination of the complexity, and the development of exact or approximate solution methods is offered.