| |
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 using this criterion. |