メインナビゲーションにスキップ 検索にスキップ メインコンテンツにスキップ

Optimal matroid partitioning problems

  • Yasushi Kawase
  • , Kei Kimura
  • , Kazuhisa Makino
  • , Hanna Sumita

研究成果: 書籍/レポート タイプへの寄稿 › 会議への寄与

1   !!Link opens in a new tab 被引用数 (Scopus)

抄録

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.

本文言語英語
ホスト出版物のタイトル28th International Symposium on Algorithms and Computation, ISAAC 2017
編集者Takeshi Tokuyama, Yoshio Okamoto
出版社Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(電子版)9783959770545
DOI
出版ステータス出版済み - 12月 1 2017
外部発表はい
イベント28th International Symposium on Algorithms and Computation, ISAAC 2017 - Phuket, タイ
継続期間: 12月 9 2017 → 12月 22 2017

出版物シリーズ

名前Leibniz International Proceedings in Informatics, LIPIcs
巻92
ISSN(印刷版)1868-8969

その他

その他28th International Symposium on Algorithms and Computation, ISAAC 2017
国/地域タイ
CityPhuket
Period12/9/17 → 12/22/17

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア

フィンガープリント

「Optimal matroid partitioning problems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル