2023/11/20 by Siyue Liu, Chao Xu, Liu, Siyue +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2311.11737
openalex publication_date 2023/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a matroid where all elements are labeled with an element in ℤ. 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(24m n r5/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.