Optimal Matroid Partitioning Problems
Optimal Matroid Partitioning Problems
复制标题
DOI：
10.1007/s00453-021-00797-9
复制
发表时间：
2017-10
期刊：
影响因子：
1.1
通讯作者：
Yasushi Kawase;Kei Kimura;K. Makino;Hanna Sumita
中科院分区：
文献类型：
--
作者：
Yasushi Kawase;Kei Kimura;K. Makino;Hanna Sumita
本文研究了不同目标函数下的最优拟阵划分问题。在这个问题中，我们被赋予在同一个基集上的加权拟阵。我们的目标是找到一个可行的分区，最小化（最大化）的目标函数的值。一个典型的目标是最大的所有子集中的元素的总重量在一个子集，这是广泛研究的调度文献。同样，作为目标函数，我们处理子集中元素的最大/最小/总权重的所有子集上的最大/最小/总和。在本文中，我们确定了上述目标函数的最优划分问题的计算复杂性。也就是说，对于每个目标函数，我们要么提供一个多项式时间算法或证明NP-困难。我们还讨论了NP-难情形的逼近性。
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are givenkweighted-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.