TY - GEN
T1 - Optimal matroid partitioning problems
AU - Kawase, Yasushi
AU - Kimura, Kei
AU - Makino, Kazuhisa
AU - Sumita, Hanna
N1 - Funding Information:
∗ A full version of the paper is available at [14], https://arxiv.org/abs/1710.00950. † The first author is supported by JSPS KAKENHI Grant Number JP16K16005. ‡ The second author is supported by JSPS KAKENHI Grant Number JP15H06286.0 § The third author is supported by JSPS KAKENHI Grant Number JP24106002, JP25280004, JP26280001, and JST CREST Grant Number JPMJCR1402, Japan. ¶ The forth author is supported by JST ERATO Grant Number JPMJER1201, Japan.
PY - 2017/12/1
Y1 - 2017/12/1
N2 - This paper studies optimal matroid partitioning problems for various objective functions. Inthe problem, we are given a finite set E and k weighted matroids (E, Ii,wi), i = 1, . . . , k, andour task is to find a minimum partition (I1, . . . , Ik) of E such that Ii 2 Ii for all i. For eachobjective function, we give a polynomial-Time algorithm or prove NP-hardness. In particular, forthe case when the given weighted matroids are identical and the objective function is the sum ofthe maximum weight in each set (i.e.,Pk i=1 maxe2Ii wi(e)), we show that the problem is strongly NP-hard but admits a PTAS.
AB - This paper studies optimal matroid partitioning problems for various objective functions. Inthe problem, we are given a finite set E and k weighted matroids (E, Ii,wi), i = 1, . . . , k, andour task is to find a minimum partition (I1, . . . , Ik) of E such that Ii 2 Ii for all i. For eachobjective function, we give a polynomial-Time algorithm or prove NP-hardness. In particular, forthe case when the given weighted matroids are identical and the objective function is the sum ofthe maximum weight in each set (i.e.,Pk i=1 maxe2Ii wi(e)), we show that the problem is strongly NP-hard but admits a PTAS.
UR - http://www.scopus.com/inward/record.url?scp=85038584084&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038584084&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2017.51
DO - 10.4230/LIPIcs.ISAAC.2017.51
M3 - Conference contribution
AN - SCOPUS:85038584084
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 28th International Symposium on Algorithms and Computation, ISAAC 2017
A2 - Tokuyama, Takeshi
A2 - Okamoto, Yoshio
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 28th International Symposium on Algorithms and Computation, ISAAC 2017
Y2 - 9 December 2017 through 22 December 2017
ER -