|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||Abstract:||
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.
|Library ID:||AC05036947||Organisation:||E184 - Institut für Informationssysteme||Publication Type:||Thesis
|Appears in Collections:||Thesis|
Show full item record
Files in this item:
|Hypertree decompositions for optimal winner determination in combinatorial auctions.pdf||777.6 kB||Adobe PDF|
checked on Feb 18, 2021
checked on Feb 18, 2021
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.