Gesellschaft für Informatik e.V.

Lecture Notes in Informatics


INFORMATIK 2008 Beherrschbare Systeme - dank Informatik Band 2 P-134, 541-546 (2008).

Gesellschaft für Informatik, Bonn
2008


Editors

Heinz-Gerd Hegering (ed.), Axel Lehmann (ed.), Hans Jürgen Ohlbach (ed.), Christian Scheideler (ed.)


Copyright © Gesellschaft für Informatik, Bonn

Contents

Computational Complexity in Constraint-based Combinatorial Auctions

Michael Thomas Egner and Walter Hower

Abstract


This paper analyzes the dynamic programming construction of bundles within the framework of the Winner Determination Problem in Combinatorial Auctions, based on constraint processing. We discuss different approaches to its representation and highlight the corresponding complexity, employing suitable combinatorics from Discrete Mathematics. Our view may enlighten us about the exponential search space-and incidentally pointing to appropriate techniques to cope with this challenge.


Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-228-4


Last changed 04.10.2013 18:18:33