Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2310.05147 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917748465991680 |
|---|---|
| author | Hausbrandt, Nils Bachtler, Oliver Ruzika, Stefan Schäfer, Luca E. |
| author_facet | Hausbrandt, Nils Bachtler, Oliver Ruzika, Stefan Schäfer, Luca E. |
| contents | We introduce the parametric matroid one-interdiction problem. Given a matroid, each element of its ground set is associated with a weight that depends linearly on a real parameter from a given parameter interval. The goal is to find, for each parameter value, one element that, when being removed, maximizes the weight of a minimum weight basis. The complexity of this problem can be measured by the number of slope changes of the piecewise linear function mapping the parameter to the weight of the optimal solution of the parametric matroid one-interdiction problem. We provide two polynomial upper bounds as well as a lower bound on the number of these slope changes. Using these, we develop algorithms that require a polynomial number of independence tests and analyse their running time in the special case of graphical matroids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05147 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Parametric Matroid Interdiction Hausbrandt, Nils Bachtler, Oliver Ruzika, Stefan Schäfer, Luca E. Combinatorics We introduce the parametric matroid one-interdiction problem. Given a matroid, each element of its ground set is associated with a weight that depends linearly on a real parameter from a given parameter interval. The goal is to find, for each parameter value, one element that, when being removed, maximizes the weight of a minimum weight basis. The complexity of this problem can be measured by the number of slope changes of the piecewise linear function mapping the parameter to the weight of the optimal solution of the parametric matroid one-interdiction problem. We provide two polynomial upper bounds as well as a lower bound on the number of these slope changes. Using these, we develop algorithms that require a polynomial number of independence tests and analyse their running time in the special case of graphical matroids. |
| title | Parametric Matroid Interdiction |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.05147 |