Towards Better Approximation of Winner Determination for Combinatorial Auctions with Large Number of Bids
Towards Better Approximation of Winner Determination for Combinatorial Auctions with Large Number of Bids
复制标题
更好地近似确定大量出价的组合拍卖的获胜者
DOI：
10.1109/iat.2006.123
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Takayuki Ito
中科院分区：
文献类型：
--
作者：
Naoki Fukuta;Takayuki Ito
我们提出了新的近似算法的组合拍卖大量（超过100,000）出价。在本文中，我们专注于一个更实用的近似算法的收入最大化的背景下。我们提出了一个爬山贪婪算法，SA样随机搜索算法，以及它们的增强搜索多个关键参数值。实验结果表明，我们的算法执行约0.997的最优性与最优解相比，优于以前提出的近似算法。我们还证明了我们的算法是一种随时算法，带来更好的结果，在较短的计算时间，可以应用于大型和动态的电子市场。
We propose new approximate algorithms for combinatorial auctions with massively large number of (more than 100,000) bids. In this paper, we focus on a more practical approximated algorithm in the context of revenue maximization. We propose a hill-climbing greedy algorithm, a SA-like random search algorithm, and their enhancement for searching multiple key parameter values. The experimental results demonstrate that our algorithms perform approximately 0.997 optimality compared with the optimal solutions and better than previously presented approximated algorithms. We also demonstrate that our algorithms are a kind of anytime algorithm that bring better results in shorter computational time that can be applied to large and dynamic electronic markets.