講演抄録/キーワード |
講演名 |
2015-04-23 15:25
一般化メークスパン最小化問題の計算複雑度 ○永山恒彦・定兼邦彦(東大) COMP2015-4 |
抄録 |
(和) |
本稿では,無関連並列機械スケジューリングのメークスパン最小化問題を拡張し,一般化メークスパン最小化問題を定式化する.これは重み付き無向グラフに対し,頂点にかかる負荷の最大値を最小化する枝被覆を求める問題である.更に,この問題の計算複雑度に関する結果として,枝の重みが二通りでも NP 困難であることを示す. |
(英) |
We generalize the makespan minimization problem on unrelated parallel machines and formulate the generalized makespan minimization problem, which finds an edge cover that minimizes the maximum weighted cost on a weighted graph. We then show that this problem is NP-hard even if the number of different costs on edges is two. |
キーワード |
(和) |
グラフアルゴリズム / 計算量理論 / 枝被覆 / スケジューリング問題 / / / / |
(英) |
graph algorithm / computational complexity / edge cover / scheduling problem / / / / |
文献情報 |
信学技報, vol. 115, no. 15, COMP2015-4, pp. 21-25, 2015年4月. |
資料番号 |
COMP2015-4 |
発行日 |
2015-04-16 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2015-4 |