An experimental analysis of biased parallel greedy approximation for combinatorial auctions. (4th October 2010)

• Record Type: Journal Article
• Authors: Fukuta, Naoki; Ito, Takayuki
• Is Part Of: International journal of intelligent information and database systems. Volume 4:Number 5(2010)
• Page Start: 487
• Page End: 508
• Publication Date: 2010-10-04
• Subjects: combinatorial auctions -- approximation algorithms -- multi-agent systems -- agent-based systems -- MAS -- resource allocation -- biased parallel greedy updating; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

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.