Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.08178 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917953297973248 |
|---|---|
| author | Hausbrandt, Nils Ruzika, Stefan |
| author_facet | Hausbrandt, Nils Ruzika, Stefan |
| contents | In this article, we investigate the multi-parametric matroid problem. The weights of the elements of the matroid's ground set depend linearly on an arbitrary but fixed number of parameters, each of which is taken from a real interval. The goal is to compute a minimum weight basis for each possible combination of the parameters. For this problem, we propose an algorithm that requires a polynomial number of independence tests and discuss two useful applications. First, the algorithm can be applied to solve a multi-parametric version of a special matroid interdiction problem, and second, it can be utilized to compute the weight set decomposition of the multi-objective (graphic) matroid problem. For the latter, we asymptotically improve the current state-of-the-art algorithm by a factor that is almost proportional to the number of edges of the graphic matroid. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08178 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-parametric matroids -- Applications to interdiction and weight set decomposition Hausbrandt, Nils Ruzika, Stefan Combinatorics In this article, we investigate the multi-parametric matroid problem. The weights of the elements of the matroid's ground set depend linearly on an arbitrary but fixed number of parameters, each of which is taken from a real interval. The goal is to compute a minimum weight basis for each possible combination of the parameters. For this problem, we propose an algorithm that requires a polynomial number of independence tests and discuss two useful applications. First, the algorithm can be applied to solve a multi-parametric version of a special matroid interdiction problem, and second, it can be utilized to compute the weight set decomposition of the multi-objective (graphic) matroid problem. For the latter, we asymptotically improve the current state-of-the-art algorithm by a factor that is almost proportional to the number of edges of the graphic matroid. |
| title | Multi-parametric matroids -- Applications to interdiction and weight set decomposition |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.08178 |