Paper Info
Title
Optimal Matroid Partitioning Problems
Abstract
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given k weighted-matroids on the same ground set. Our goal is to find a feasible partition that minimizes (maximizes) the value of an objective function. A typical objective is the maximum over all subsets of the total weights of the elements in a subset, which is extensively studied in the scheduling literature. Likewise, as an objective function, we handle the maximum/minimum/sum over all subsets of the maximum/minimum/total weight(s) of the elements in a subset. In this paper, we determine the computational complexity of the optimal partitioning problem with the above-described objective functions. Namely, for each objective function, we either provide a polynomial time algorithm or prove NP-hardness. We also discuss the approximability for the NP-hard cases.
Year
DOI
Venue
2021
10.1007/s00453-021-00797-9
ALGORITHMICA
Keywords
DocType
Volume
Matroid, Partitioning problem, PTAS, NP-hardness
Journal
83
Issue
ISSN
Citations 
6
0178-4617
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Yasushi Kawase14215.31
Kei Kimura201.35
Kazuhisa Makino31088102.74
Hanna Sumita427.83