1999年8月
Algorithmic aspects of the core of combinatorial optimization games
MATHEMATICS OF OPERATIONS RESEARCH
- ,
- ,
- 巻
- 24
- 号
- 3
- 開始ページ
- 751
- 終了ページ
- 766
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1287/moor.24.3.751
- 出版者・発行元
- INST OPERATIONS RESEARCH MANAGEMENT SCIENCES
We discuss an integer programming formulation for a class of cooperative games. We focus on algorithmic aspects of the core, one of the most important solution concepts in cooperative game theory. Central to our study is a simple (but very useful) observation that the core for this class is nonempty if and only if an associated linear program has an integer optimal solution. Based on this, we study the computational complexity and algorithms to answer important questions about the cores of various games on graphs, such as maximum flow, connectivity, maximum matching, minimum vertex cover, minimum edge cover, maximum independent set, and minimum coloring.
- リンク情報
-
- DOI
- https://doi.org/10.1287/moor.24.3.751
- DBLP
- https://dblp.uni-trier.de/rec/journals/mor/DengIN99
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000083244400010&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/mor/mor24.html#journals/mor/DengIN99
- ID情報
-
- DOI : 10.1287/moor.24.3.751
- ISSN : 0364-765X
- DBLP ID : journals/mor/DengIN99
- Web of Science ID : WOS:000083244400010