2008年
Performance Analysis about Parallel Greedy Approximation on Combinatorial Auctions
INTELLIGENT AGENTS AND MULTI-AGENT SYSTEMS, PROCEEDINGS
- ,
- 巻
- 5357
- 号
- 開始ページ
- 173
- 終了ページ
- +
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
Combinatorial auctions provide suitable mechanisms for efficient allocation of resources to self-interested agents. Considering ubiquitous computing scenarios, the ability to complete an auction within a fine-grained time period without loss of allocation efficiency is in strong demand. Furthermore, to achieve such scenarios, it is very important to handle a large number of bids in an auction. Recently, we proposed an algorithm to obtain sufficient quality of winners in very short time. However, it is demanded to analyze which factor is mainly affected to obtain such a good performance. Also it is demanded to clarify the actual implementation-level performance of the algorithm compared to a major commercial-level generic problem solver. In this paper, we show our parallel greedy updating approach contributes its better performance. Furthermore, we show our approach has a certain advantage compared to a latest commercial-level implementation of generic LP solver through various experiments.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- Web of Science ID : WOS:000262709200020