2026-08-15T14:01:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8271 2024-03-06T10:41:52Z ddc:004 open_access

Optimal Matroid Partitioning Problems Kawase, Yasushi Kimura, Kei Makino, Kazuhisa Sumita, Hanna Matroids Partitioning problem PTAS NP-hardness This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set E and k weighted matroids (E, \mathcal{I}_i, w_i), i = 1, \dots, k, and our task is to find a minimum partition (I_1,\dots,I_k) of E such that I_i \in \mathcal{I}_i for all i. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., \sum_{i=1}^k\max_{e\in I_i}w_i(e)), we show that the problem is strongly NP-hard but admits a PTAS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yasushi Kawase and Kei Kimura and Kazuhisa Makino and Hanna Sumita 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.51 urn:nbn:de:0030-drops-82712 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.51 eng https://creativecommons.org/licenses/by/3.0/legalcode