An Approximation Framework for Parametric Matroid Interdiction Problems Journal: Journal of …

Nils Hausbrandt, Levin Nemesch, Stefan Ruzika · 2025

Read An Approximation Framework for Parametric Matroid Interdiction Problems Journal: Journal of … by Nils Hausbrandt, Levin Nemesch, Stefan Ruzika (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-11085.txt.

Introduction

Nils Hausbrandt, Levin Nemesch, and Stefan Ruzika study attacks on structured sets where each item's weight shifts with a set of parameters. In the basic attack game, a foe removes a fixed number of items to force the best remaining basis to be as heavy as possible. The parametric form asks for the best attack at every parameter value at once.

The authors build the first frame that lifts near-best methods for the basic game to the parametric one, with quality as close to the base method as desired. Special cases include a fully efficient scheme for split structures and a quarter-strength method for graph structures.

Catalog record

CREATORNils Hausbrandt, Levin Nemesch, Stefan Ruzika
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-11085

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Approximation Framework for Parametric Matroid Interdiction Problems Journal: Journal of … Nils Hausbrandt, Levin Nemesch, Stefan Ruzika Abstract Matroid interdiction problems are well-researched in the field of combinatorial optimization. In the matroid ℓ \ell -interdiction problem, an interdiction strategy removes a subset of cardinality ℓ \ell from the matroid’s ground set. The goal is to maximize the weight of a remaining optimal basis. 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 value, we are interested in an optimal interdiction strategy and the weight of an optimally interdicted basis. We develop the first framework for lifting approximation algorithms for the non-parametric matroid ℓ \ell -interdiction problem to its multi-parametric variant. Whenever there exists a β \beta -approximation algorithm for the non-parametric problem, we obtain an approximation algorithm for the multi-parametric problem with an approximation quality arbitrarily close to β \beta . Our method yields an FPTAS for partition matroids and a ( 1 − ε ) ​ 1 4 (1-\varepsilon)\frac{1}{4} -approximation for graphic matroids. As part of the construction, we develop the first approximation algorithm for a conventional multi-parametric optimization problem in which the parameter vector varies in an arbitrary polytope. 1 Introduction In this article, we focus on the interdiction of matroids – one of the fundamental structures of mathematics that generalizes many well-known concepts, including independence in linear algebra, cf. 37 , 39 , 35 , 29 . In the matroid interdiction problem, an interdiction budget is given and each element of the matroid’s ground set is associated with a weight and an interdiction cost. The goal is to remove a subset of the elements whose interdiction costs meet the budget while maximizing the weight of a minimum weight basis. Interdiction problems offer a highly interesting field of research in combinatorial optimization and optimization research, cf. 32 , 33 . The problems can be seen as a game between two players, called interdictor and follower . The interdictor tries to worsen the follower’s objective function value as much as possible. The interdictor’s actions, called interdiction strategies, are limited by interdiction costs and an interdiction budget. Particularly in the last decade, matroid interdiction problems have gained a lot of interest. 15 measured the perturbability of a matroid, 1 introduced bulk robustness, 24 considered the rank interdiction problem, 7 developed pseudoapproximations, 34 constructed supervalid inequalities, 25 focused on a special class of partition matroids, 36 provide a dynamic programming approach and 19 , 20 , 21 extended to (multi-)parametric variants. Note that there is a lot of literature on the special case of minimum spanning tree interdiction, see e.g. 14 , 4 , 40 , and that we focus on arbitrary matroids here. If all interdiction costs are equal to one and the budget equals a fixed natural number \ell\in\mathbb{N}_{>0} , the matroid interdiction problem can be solved exactly in polynomial time if an independence test can be performed in time polynomial in the input length, cf. 20 , 36 . However, if \ell is considered as part of the input of the problem, the problem is \mathsf{NP} -hard - even for graphic matroids, see 14 . For the two special cases of uniform matroids and partition matroids, it is known that this variant can be solved in polynomial time, cf. 36 . For the general variant with arbitrary interdiction costs and budget, the matroid interdiction problem is \mathsf{NP} -hard for uniform, partition and graphic matroids, cf. 14 , 36 . For graphic matroids, 40 constructed an approximation algorithm with constant factor guarantee, which was improved by 26 to a \nicefrac{{1}}{{4}} -approximation. In this article, we consider a multi-parametric variant of the matroid interdiction problem where the weights of the elements of the matroid’s ground set depend linearly on a fixed p\in\mathbb{N}_{>0} of parameters coming from a parameter polytope \Lambda\subseteq\mathbb{R}^{p} , which is defined by an intersection of half-spaces. The goal is to compute, for each possible parameter vector \lambda\in\Lambda , an optimal interdiction strategy and the weight of the optimal interdicted minimum weight basis. An optimal interdiction strategy consists of a set of \ell\in\mathbb{N}_{>0} elements whose removal increases the weight of the minimum weight basis as much as possible. Parametric optimization is an active and growing field of research since at least 1970, a comprehensive survey is provided by 27 . In a general parametric optimization problem, the objective function value of a feasible solution depends (often linearly) on a parameter vector. Parametric variants exist for many well-known combinatorial optimization problems, among them minimum spanning trees and more general matroid problems, cf. 12 , 13 , 2 . The combination of parametric optimization and interdiction of matroids is a recent development. The literature so far considers the special cases where the interdiction budget equals one or a fixed natural number \ell , cf. 19 , 20 , 21 . We build upon this literature and extend it by investigating the multi-parametric matroid \ell -interdiction problem where all interdiction costs are equal to one and the budget is given by a natural number \ell\in\mathbb{N}_{>0} which is part of the input of the problem. To assess the complexity of the problem, it is necessary to consider intractability, approximability, and the complexity of the corresponding non-parametric problem. As mentioned above, the non-parametric problem, i. e. the problem in which the parameter is fixed to a vector \lambda\in\Lambda , is \mathsf{NP} -hard. It is unknown whether the multi-parametric matroid \ell -interdiction problem is intractable or not, i. e. whether it requires a super-polynomial number of optimal interdiction strategies when the parameter vector varies within the parameter polytope \Lambda . Our goal is to provide a significant step toward understanding the complexity of the problem. We show that approximation algorithms for the corresponding non-parametric problem can be lifted to the multi-parametric problem. To achieve this, we combine structural results for matroid \ell -interdiction problems with a new multi-parametric approximation algorithm. As a result, we provide the first approximation algorithm for a (multi-)parametric interdiction problem. More precisely, we show that whenever there exists a polynomial time \beta -approximation algorithm for the non-parametric matroid \ell -interdiction problem ( 0<\beta\leq 1 ), there exists a polynomial time approximation algorithm for the multi-parametric variant with approximation guarantee arbitrary close to \beta . More specifically, we assume that there exists an oracle \mathsf{ORC}_{\beta} that computes, for a fixed parameter vector \lambda\in\Lambda , a \beta -approximate interdiction strategy at \lambda . This is a subset of the matroid’s ground set that contains \ell elements whose removal results in a minimum weight basis with a weight that is at most a factor of \beta smaller than the weight of an optimal \ell -interdicted minimum weight basis. Two prominent matroid interdiction problems that satisfy the assumption are the partition as well as the graphic matroid interdiction problem. Given the oracle \mathsf{ORC}_{\beta} , we develop an algorithm that computes, for a given 0<\varepsilon<1 , a (1-\varepsilon)\beta -approximation on the entire parameter polytope \Lambda . Such an approximation consists of a decomposition of the parameter polytope into smaller polytopes and one interdiction strategy per polytope which is (1-\varepsilon)\beta -approximate for all vectors within the polytope. To lift

Read the complete text