2026-07-21T10:22:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20243 2024-07-02T07:52:53Z ddc:004 open_access

Subquadratic Submodular Maximization with a General Matroid Constraint Kobayashi, Yusuke Terao, Tatsuya submodular maximization matroid constraint approximation algorithm rounding algorithm query complexity We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized (1 - 1/e - ε)-approximation algorithm that requires Õ_{ε}(√r n) independence oracle and value oracle queries, where n is the number of elements in the matroid and r ≤ n is the rank of the matroid. This improves upon the previously best algorithm by Buchbinder-Feldman-Schwartz [Mathematics of Operations Research 2017] that requires Õ_{ε}(r² + √rn) queries. Our algorithm is based on continuous relaxation, as with other submodular maximization algorithms in the literature. To achieve subquadratic query complexity, we develop a new rounding algorithm, which is our main technical contribution. The rounding algorithm takes as input a point represented as a convex combination of t bases of a matroid and rounds it to an integral solution. Our rounding algorithm requires Õ(r^{3/2} t) independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondrák-Zenklusen [FOCS 2010] requires O(r² t) independence oracle queries. A key idea in our rounding algorithm is to use a directed cycle of arbitrary length in an auxiliary graph, while the algorithm of Chekuri-Vondrák-Zenklusen focused on directed cycles of length two. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yusuke Kobayashi and Tatsuya Terao 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.100 urn:nbn:de:0030-drops-202437 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.100 eng https://creativecommons.org/licenses/by/4.0/legalcode