تقرير
Fast Algorithms via Dynamic-Oracle Matroids
| العنوان: | Fast Algorithms via Dynamic-Oracle Matroids |
|---|---|
| المؤلفون: | Blikstad, Joakim, Mukhopadhyay, Sagnik, Nanongkai, Danupon, Tu, Ta-Wei |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity |
| الوصف: | We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" algorithm whose performance matches previous results developed in various papers. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. * We show an algorithm with $\tilde{O}_k(n+r\sqrt{r})$ dynamic-rank-query and time complexities for the matroid union problem over $k$ matroids. This implies the following consequences. (i) An improvement over the $\tilde{O}_k(n\sqrt{r})$ bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An $\tilde{O}_k(|E|+|V|\sqrt{|V|})$-time algorithm for the $k$-disjoint spanning tree problem. This improves the $\tilde{O}_k(|V|\sqrt{|E|})$ bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. * We show a matroid intersection algorithm with $\tilde{O}(n\sqrt{r})$ dynamic-rank-query and time complexities. This implies new bounds for some problems and bounds that match the classic ones obtained in various papers, e.g. colorful spanning tree [Gabow-Stallmann ICALP'85], graphic matroid intersection [Gabow-Xu FOCS'89], simple scheduling matroid intersection [Xu-Gabow ISAAC'94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a "unified" algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. * We show simple super-linear ($\Omega(n\log n)$) query lower bounds for matroid intersection in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous $\log_2(3)n - o(n)$ bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19]. Comment: To appear at STOC 2023. Abstract shortened to meet arXiv requirement |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2302.09796 |
| رقم الأكسشن: | edsarx.2302.09796 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |