On the Congruency-Constrained Matroid Base
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916169098723328 |
|---|---|
| author | Liu, Siyue Xu, Chao |
| author_facet | Liu, Siyue Xu, Chao |
| contents | Consider a matroid where all elements are labeled with an element in $\mathbb{Z}$. We are interested in finding a base where the sum of the labels is congruent to $g \pmod m$. We show that this problem can be solved in $\tilde{O}(2^{4m} n r^{5/6})$ time for a matroid with $n$ elements and rank $r$, when $m$ is either the product of two primes or a prime power. The algorithm can be generalized to all moduli and, in fact, to all abelian groups if a classic additive combinatorics conjecture by Schrijver and Seymour holds true. We also discuss the optimization version of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_11737 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Congruency-Constrained Matroid Base Liu, Siyue Xu, Chao Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control Consider a matroid where all elements are labeled with an element in $\mathbb{Z}$. We are interested in finding a base where the sum of the labels is congruent to $g \pmod m$. We show that this problem can be solved in $\tilde{O}(2^{4m} n r^{5/6})$ time for a matroid with $n$ elements and rank $r$, when $m$ is either the product of two primes or a prime power. The algorithm can be generalized to all moduli and, in fact, to all abelian groups if a classic additive combinatorics conjecture by Schrijver and Seymour holds true. We also discuss the optimization version of the problem. |
| title | On the Congruency-Constrained Matroid Base |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2311.11737 |