Title: Hypertree decompositions for optimal winner determination in combinatorial auctions
Language: English
Authors: Lebedeva, Ekaterina 
Qualification level: Diploma
Keywords: Kombinatorische Auktionen; Hypertree Dekompositionen
Combinatorial Auctions; Hypertree Decompositions; Constraint Satisfaction Problems
Advisor: Gottlob, Georg
Assisting Advisor: Musliu, Nysret 
Issue Date: 2008
Number of Pages: 63
Qualification level: Diploma
A combinatorial auction is an auction in which various items are sold and a bid can be placed for more than one item at once. The winner determination problem for a combinatorial auction is the task of determining a set of mutually disjoint bids that brings the maximal revenue from the auction. This problem is known to be NP-complete.
To cope with the NP-completeness of the winner determination problem for general combinatorial auctions, there were attempts to identify the most general classes of combinatorial auction instances on which the problem is feasible in polynomial time. One of these attempts resulted in a polynomial time algorithm for combinatorial auction instances with associated dual hypergraphs having the hypertree width bounded by some natural number.
In this thesis we describe the essential concepts involved in solving the winner determination problem by means of the ComputeSetPackingK algorithm, which is a polynomial time algorithm that utilizes the notion of hypertree decomposition. We implemented the algorithm, and the description of our implementation is given in the thesis. The experimental evaluation of our implementation showed how the essential parameters of the combinatorial auctions (distributions used for generating problem instances, numbers of items and bids) and of the decomposition method (the width and the size of the constructed hypertree) influence the performance of the algorithm. The results and analysis of our experimental tests, as well as a comparison of ComputeSetPackingK with the other approaches for different distributions with respect to their hardness to be solved, are also presented within the thesis.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-28719
Library ID: AC05036947
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.