Consider a matroid where all elements are labeled with an element from $\mathbb{Z}_m$. 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 $O(m^{2m} n r \log r)$ 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 generalizes to all moduli, and in fact, to all abelian groups, if a classic additive combinatorics conjecture of Schrijver and Seymour is true. We also discuss the optimization version of the problem.
翻译:暂无翻译