An efficient approximate allocation algorithm for combinatorial auctions
An efficient approximate allocation algorithm for combinatorial auctions
复制标题
一种高效的组合拍卖近似分配算法
DOI：
10.1145/501158.501172
复制
发表时间：
2001
影响因子：
6.8
通讯作者：
N. Nisan
中科院分区：
文献类型：
--
作者：
Edo Zurel;N. Nisan
我们提出了组合拍卖中分配的启发式。我们首先在组合拍卖的线性编程松弛上运行近似算法。然后，我们运行了一系列贪婪的算法，从近似线性程序确定的竞标顺序开始，然后使用竞标顺序进行本地改进以爬山方式继续进行。我们已经实施了该算法，并在Vohra和de Vries提供的完整实例以及从Leyton-Brown，Pearson和Shoham的分布中进行了对其进行了测试。我们的算法通常比报道的Vohra和de Vries的运行时间快两到三个数量级，而平均近似误差小于1％。该算法可以在不到一分钟的CPU时间内提供出色的解决方案，以解决超过1000个项目和10,000个投标的问题。因此，我们认为，用于大多数目的的组合拍卖没有任何实际的计算障碍。
We propose a heuristic for allocation in combinatorial auctions. We first run an approximation algorithm on the linear programming relaxation of the combinatorial auction. We then run a sequence of greedy algorithms, starting with the order on the bids determined by the approximate linear program and continuing in a hill-climbing fashion using local improvements in the order of bids. We have implemented the algorithm and have tested it on the complete corpus of instances provided by Vohra and de Vries as well as on instances drawn from the distributions of Leyton-Brown, Pearson, and Shoham. Our algorithm typically runs two to three orders of magnitude faster than the reported running times of Vohra and de Vries, while achieving an average approximation error of less than 1%. This algorithm can provide, in less than a minute of CPU time, excellent solutions for problems with over 1000 items and 10,000 bids. We thus believe that combinatorial auctions for most purposes face no practical computational hurdles.