Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2408.07546 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916357196480512 |
|---|---|
| author | Hausbrandt, Nils Ruzika, Stefan |
| author_facet | Hausbrandt, Nils Ruzika, Stefan |
| contents | In this article, we introduce the parametric matroid $\ell$-interdiction problem, where $\ell\in\mathbb{N}_{>0}$ is a fixed number of elements allowed to be interdicted. Each element of the matroid's ground set is assigned a weight that depends linearly on a real parameter from a given interval. The goal is to compute, for each possible parameter value, a set of $\ell$-most vital elements with corresponding objective value the deletion of which causes a maximum increase of the weight of a minimal basis. We show that such a set, which of course depends on the parameter, can only change polynomially often if the parameter varies. We develop several exact algorithms to solve the problem that have polynomial running times if an independence test can be performed in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Parametric Matroid $\ell$-Interdiction Problem Hausbrandt, Nils Ruzika, Stefan Combinatorics In this article, we introduce the parametric matroid $\ell$-interdiction problem, where $\ell\in\mathbb{N}_{>0}$ is a fixed number of elements allowed to be interdicted. Each element of the matroid's ground set is assigned a weight that depends linearly on a real parameter from a given interval. The goal is to compute, for each possible parameter value, a set of $\ell$-most vital elements with corresponding objective value the deletion of which causes a maximum increase of the weight of a minimal basis. We show that such a set, which of course depends on the parameter, can only change polynomially often if the parameter varies. We develop several exact algorithms to solve the problem that have polynomial running times if an independence test can be performed in polynomial time. |
| title | The Parametric Matroid $\ell$-Interdiction Problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.07546 |