Back to Search Start Over

Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics

Authors :
Gonen, Rica
Lehmann, Daniel
Gonen, Rica
Lehmann, Daniel
Publication Year :
2002

Abstract

Finding optimal solutions for multi-unit combinatorial auctions is a hard problem and finding approximations to the optimal solution is also hard. We investigate the use of Branch-and-Bound techniques: they require both a way to bound from above the value of the best allocation and a good criterion to decide which bids are to be tried first. Different methods for efficiently bounding from above the value of the best allocation are considered. Theoretical original results characterize the best approximation ratio and the ordering criterion that provides it. We suggest to use this criterion.<br />Comment: Presented at EC'00

Details

Database :
OAIster
Publication Type :
Electronic Resource
Accession number :
edsoai.ocn691108864
Document Type :
Electronic Resource