文献

J-GLOBAL ID：201202223046482588   整理番号：12A0626975

二次効用関数を用いた最適割当問題と,グラフカット問題とそれの関係

OPTIMAL ALLOCATION PROBLEM WITH QUADRATIC UTILITY FUNCTIONS AND ITS RELATIONSHIP WITH GRAPH CUT PROBLEM

著者 (2件)： SHIOURA Akiyoshi (Tohoku Univ.) ,  SUZUKI Shunya (Tohoku Univ.)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 55  号： 1  ページ： 92-105  発行年： 2012年03月 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 入札者の効用和が最大化されるように入札者にアイテムが割当てられる場合を想定し,そのような組合せオークションにおける最適割当問題を取り上げて論じた。本論文では,二次関数により効用関数が与えられる場合のケースを考察した。即ち,そのような効用関数のクラスは簡潔な表現を持つが,十分一般性を備えている。二次効用関数を用いた最適割当問題の計算量を示すことが本論文の主要目的である。ここでは,効用関数が劣モジュラおよび超モジュラであるようなケースを取り上げて考察し,NP困難性および/または多項式高精度/近似的アルゴリズムを示した。これらの結果は,ミニまたはマックスカット問題およびマルチウェイカット問題のようなグラフカット問題との関係を用いることにより示した。(翻訳著者抄録)

シソーラス用語： 取引 ,  *入札 ,  *割当問題 ,  最適化問題 ,  効用関数 ,  *計算量 ,  アルゴリズム ,  NP困難 ,  精度 ,  計算機アルゴリズム ,  最大化問題 ,  画像処理
準シソーラス用語： *組合せオークション ,  *最適割当問題 ,  近似アルゴリズム ,  マックスカット問題 ,  グラフカット

分類 (3件)： 利益管理  (KA05030A) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  計算理論  (JB02000A)

引用文献 (28件)：

• 1) AHUJA R. K. Network Flows : Theory, Algorithms, and Applications. Prentice Hall. (1993)
• 2) BLUMROSEN L. Combinatorial auction. Algorithmic Game Theory. Cambridge University Press. (2007) p.267-299.
• 3) CHEVALEYRE Y. Multiagent resource allocation in κ-additive domains : preference representation and complexity. Annals of Operations Research. (2008) vol.163, p.49-62.
• 4) CONITZER V. Combinatorial auctions with k-wise dependent valuations. Proceedings of 20th National Conference on Artificial Intelligence (AAAI), 2005. (2005) p.248-254.
• 5) CRAMTON P. Combinatorial Auctions. MIT Press. (2006)

タイトルに関連する用語 (4件)： 効用関数 ,  割当問題 ,  グラフカット ,  問題