Combinatorial Auctions and Knapsack Problems - An Analysis of Optimization Methods

ISBN-13: 9783836450065 / Angielski / Miękka / 2007 / 128 str.

Jella Pfeiffer

Opis

With the rapid diffusion of the internet, different kinds of market designs fore-commerce have emerged. Among these, combinatorial auctions (CAs) havegained increased interest as they permit bidders to express their valuationsmore easily. For applying a CA in real world scenarios, fast algorithms areneeded to compute the optimal allocation of the offered goods. Althoughmuch research has dealt with this so-called Winner Determination Problem(WDP), only recently has its equivalence to the well-studied multi-dimensionalknapsack problem (MDKP) been noticed. Therefore, there is a lack of researchwhich compares approaches for solving MDKP and WDP problems. With thiswork, the author, Jella Pfeiffer, provides the missing integrative step, aimingat a more intense understanding and a mutual inspiration of both researchareas. She examines structural differences of test instances from bothdomains, compares the performance of different algorithms, and alludes to asuccessful search behavior of non-exact but fast algorithms. The bookaddresses readers interested in electronic market design and algorithmssolving complex combinatorial optimization problems.