| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 4A |
| セッション名 |
| 最適化 |
| 講演日 |
| 2009/09/03 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-019 |
| タイトル |
| 2次の効用関数に関する不可分財の最適配分問題 : 計算複雑度とアルゴリズム |
| 著者名 |
| 塩浦 昭義, 鈴木 瞬也, 吉田 卓司, |
| キーワード |
| 組合せオークション, 劣モジュラ関数, 優モジュラ関数, 離散凸関数, 組合せ最適化, NP困難 |
| 抄録 |
| 本講演では,不可分財に対する組合せオークションから生じる財の配分問題について考える.この配分問題では,m人の参加者に対し,n個の不可分財を配分する.参加者の効用関数値の和を最大化するような配分を求めることが目的である.本講演では,効用関数が2次の集合関数により与えられる配分問題において,効用関数が優モジュラや劣モジュラなどの性質をもつ場合,また参加者が2人の場合と3人以上の場合を考え,それぞれの場合において問題のNP困難性,または多項式時間可解性を示す.多項式時間で解ける場合については,効率的なアルゴリズムを提案する. |
| 本文pdf |
| PDF download (134.4KB) |