In the matroid partitioning problem, we are given \(k\) matroids \(\mathcal{M}_{1}=(V,\mathcal{I}_{1}),\dots,\mathcal{M}_{k}=(V,\mathcal{I}_{k})\) defined over a common ground set \(V\) of \(n\) elements, and we need to find a partitionable set \(S\subseteq V\) of largest possible cardinality, denoted by \(p\) . Here, a set \(S\subseteq V\) is called partitionable if there exists a partition \((S_{1},\dots,S_{k})\) of \(S\) with \(S_{i}\in\mathcal{I}_{i}\) for \(i=1,\ldots,k\) . In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses \(O(np^{3/2}+kn)\) independence oracle queries, which was the previously known best algorithm. This query complexity is \(O(n^{5/2})\) when \(k\leq n\) . Our main result is to present a matroid partition algorithm that uses \(\tilde{O}(k^{\prime 1/3}np+kn)\) independence oracle queries, where \(k^{\prime}=\min\{k,p\}\) . This query complexity is \(\tilde{O}(n^{7/3})\) when \(k\leq n\) , which improves upon that of Cunningham’s algorithm. To obtain our algorithm, we present a new approach edge recycling augmentation , which can be attained through new ideas: an efficient utilization of the binary search technique by Nguy \(\tilde{{\hat{\text{e}}}}\) n [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019] and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter \(k\) . We also present a matroid partition algorithm that uses \(\tilde{O}((n+k)\sqrt{p})\) rank oracle queries.

Tatsuya Terao

ACM Transactions on Algorithms

ACM TRANSACTIONS ON ALGORITHMS 欢迎提交最高质量的原始研究，处理本质上离散和有限的算法，并且在目标或分析中以自然的方式具有数学内容。最受欢迎的是新算法和数据结构、新的和改进的分析以及复杂性结果。该杂志涵盖的具体计算领域包括组合搜索和对象；计数；离散优化和近似；随机化和量子计算；并行和分布式计算；图形算法、几何、算术、数论、字符串；在线分析；密码学；编码;数据压缩;学习算法;算法分析方法;离散算法应用于生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等应用领域

ACM Transactions on Algorithms welcomes submissions of high-quality original research that deals with discrete and finite algorithms, naturally incorporating mathematical content in its objectives or analyses. We particularly encourage new algorithms and data structures, novel and improved analyses, and complexity results. The specific computational areas covered by the journal include combinatorial search and objects, counting, discrete optimization and approximation, randomized and quantum computing, parallel and distributed computing, graph algorithms, geometry, arithmetic, number theory, string processing, online analysis, cryptography, coding, data compression, learning algorithms, algorithmic analysis methods, and the application of discrete algorithms in fields such as biology, economics, game theory, communications, computer systems and architecture, hardware design, and scientific computing.

《ACM Transactions on Algorithms》欢迎提交高质量的原创研究，主要涉及离散和有限算法，且在目标或分析中自然包含数学内容。我们特别欢迎新算法和数据结构的提出、新的和改进的分析方法，以及复杂性结果的研究。该期刊涵盖的具体计算领域包括组合搜索与对象、计数、离散优化与近似、随机化与量子计算、并行与分布式计算、图算法、几何、算术、数论、字符串处理、在线分析、密码学、编码、数据压缩、学习算法、算法分析方法，以及离散算法在生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等领域的应用。

Category	Quartile
计算机科学	3
计算机科学, 计算机理论方法	2
计算机科学, 应用数学	2

Faster Matroid Partition Algorithms

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
MATHEMATICS, APPLIED	3