WEKO3
アイテム
組合せ最適化ゲーム
https://ipsj.ixsq.nii.ac.jp/records/32246
https://ipsj.ixsq.nii.ac.jp/records/3224692755f77-2aa6-453b-88de-0eef36c36be2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL96055003.pdf (662.6 kB)
|
Copyright (c) 1997 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1997-01-23 | |||||||
| タイトル | ||||||||
| タイトル | 組合せ最適化ゲーム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Combinatorial Optimization Games | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 値 | ヨーク大学計算機科学科 | |||||||
| 著者所属 | ||||||||
| 値 | 京都大学工学研究科数理工学教室 | |||||||
| 著者所属 | ||||||||
| 値 | 京都大学工学研究科数理工学教室 | |||||||
| 著者所属(英) | ||||||||
| 言語 | en | |||||||
| 値 | York University | |||||||
| 著者所属(英) | ||||||||
| 言語 | en | |||||||
| 値 | Kyoto University | |||||||
| 著者所属(英) | ||||||||
| 言語 | en | |||||||
| 値 | Kyoto University | |||||||
| 著者名 |
デンシャオティエ
× デンシャオティエ
|
|||||||
| 著者名(英) |
Xiaotie, Deng
× Xiaotie, Deng
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | あるクラスの組合せ最適化問題ゲームを記述する01?整数計画問題を用いた協力ゲームの新しい定式化を導入する。多くの興味深いグラフ問題のゲームがこの定式化により記述できる。新しい定式化による重要な一般的結果として、このクラスに属するゲームがコア（協力ゲーム理論の解の概念の1つ）を持つかどうかが、対応する01?整数計画問題が整数制約なしで整数最適解を持つことと同値であることを示す。この数学的条件がグラフ問題において成立するための性質を調べ、それらのコアにを求める算法、計算量に関する次のような問題について考察する：コアが存在するかどうかの決定、コアが存在する場合に1つのコアを求める、与えられた配分がコアかどうかの判定など。例えば、新しい定式化に基づく結果を用いれば、単位ネットワーク上のフローゲームのコアを凸分解する多項式時間の算法を構築することができる。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We introduce a general integer programming formulation for a class of combination optimization games, which include many interesting problems on graphs. The formulation immediately allows us to improve the algorithmic result for finding imputations in the core (an important solution concept in cooperative game theory) of the network flow game on unit networks. An important result is a general theorem that the core for this class of games is nonempty if and only if a related linear program has an integer optimal solution. We study the properties for this mathematical condition to hold for several problems on graphs, and apply them to resolve algorithmic and complexity issues for their cores: decide whether the core is empty; if the core is empty, find an imputation in the core; given an imputation x, test whether x is in the core. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1997, 号 8(1996-AL-055), p. 21-28, 発行日 1997-01-23 |
|||||||
| Notice | ||||||||
| 値 | SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
