License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.104
URN: urn:nbn:de:0030-drops-181566
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18156/
Go to the corresponding LIPIcs Volume Portal

Terao, Tatsuya

Faster Matroid Partition Algorithms

pdf-format:
LIPIcs-ICALP-2023-104.pdf (0.8 MB)

Abstract

In the matroid partitioning problem, we are given k matroids ℳ₁ = (V, ℐ_1), … , ℳ_k = (V, ℐ_k) defined over a common ground set V of n elements, and we need to find a partitionable set S ⊆ V of largest possible cardinality, denoted by p. Here, a set S ⊆ V is called partitionable if there exists a partition (S_1, … , S_k) of S with S_i ∈ ℐ_i for i = 1, …, k. In 1986, Cunningham [Cunningham, 1986] presented a matroid partition algorithm that uses O(n p^{3/2} + k n) independence oracle queries, which was the previously known best algorithm. This query complexity is O(n^{5/2}) when k ≤ n.
Our main result is to present a matroid partition algorithm that uses Õ(k^{1/3} n p + k n) independence oracle queries, which is Õ(n^{7/3}) when k ≤ n. This improves upon previous Cunningham’s algorithm. To obtain this, 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ễn [Nguyen, 2019] and Chakrabarty-Lee-Sidford-Singla-Wong [Chakrabarty et al., 2019] and a careful analysis of the number of independence oracle queries. 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 Õ((n + k) √p) rank oracle queries.

BibTeX - Entry

@InProceedings{terao:LIPIcs.ICALP.2023.104,
  author =	{Terao, Tatsuya},
  title =	{{Faster Matroid Partition Algorithms}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18156},
  URN =		{urn:nbn:de:0030-drops-181566},
  doi =		{10.4230/LIPIcs.ICALP.2023.104},
  annote =	{Keywords: Matroid Partition, Matroid Union, Combinatorial Optimization}
}

Keywords: Matroid Partition, Matroid Union, Combinatorial Optimization
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI