Title: An experimental analysis of biased parallel greedy approximation for combinatorial auctions

Authors: Naoki Fukuta, Takayuki Ito

Addresses: Department of Computer Science, Faculty of Informatics, Shizuoka University, 3 5 1 Johoku Nakaku Hamamatsu, 4328011, Japan. ' Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology, Gokisocho Showa Nagoya, 4668555, Japan

Abstract: 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.

Keywords: combinatorial auctions; approximation algorithms; multi-agent systems; agent-based systems; MAS; resource allocation; biased parallel greedy updating.

DOI: 10.1504/IJIIDS.2010.035773

International Journal of Intelligent Information and Database Systems, 2010 Vol.4 No.5, pp.487 - 508

Received: 25 Jun 2009
Accepted: 13 Aug 2009
Published online: 03 Oct 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article