An experimental analysis of biased parallel greedy approximation for combinatorial auctions. (4th October 2010) - Fukuta, Naoki; Ito, Takayuki
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.