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 -