2010年10月
An experimental analysis of biased parallel greedy approximation for combinatorial auctions
International Journal of Intelligent Information and Database Systems
- ,
- 巻
- 4
- 号
- 5
- 開始ページ
- 487
- 終了ページ
- 508
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1504/IJIIDS.2010.035773
Considering emerging demands for auction based efficient resource allocations, the ability to complete an auction within a fine-grained time period without loss of allocation efficiency is in strong demand. Recently, an algorithm has been proposed to obtain near-optimal solutions for winner determination problem on combinatorial auctions within a very short computation time. However, it is demanded to analyse and clarify the main factor of such an excellent performance of the algorithm. Also, for practical use, there are demands to clarify the actual implementation-level performance of the algorithm compared to major commercial-level generic problem solvers. In this paper, we show an analysis about performance issues of biased parallel greedy updating approach in various experimental settings. Furthermore, we show that the algorithm has a certain advantage to solve a kind of large-size high-complexity problems when it is compared to a latest commercial-level implementation of generic LP solver through various experiments. © 2010 Inderscience Enterprises Ltd.
- ID情報
-
- DOI : 10.1504/IJIIDS.2010.035773
- ISSN : 1751-5858
- ISSN : 1751-5866
- SCOPUS ID : 77957746611