Hypertree Decompositions for Combinatorial Auctions - Optimal Winner Determination

ISBN-13: 9783639022315 / Angielski / Miękka / 2008 / 80 str.

Ekaterina Lebedeva

Opis

Combinatorial auctions are auctions in which each bid can be placed on a set of items, as opposed to standard auctions, in which each bid is placed on a single item. The winner determination problem for combinatorial auctions is known to be NP-complete. One of the approaches to cope with the hardness of the problem is to identify tractable classes of combinatorial auctions by means of hypertree decompositions. The winner determination problem is tractable on the class of instances with corresponding dual hypergraphs having hypertree width bounded by a fixed natural number. This book describes an optimal algorithm, called ComputeSetPackingK, for solving the winner determination problem based on these ideas. The algorithm was implemented, and experimental results are also presented.

O autorze

LEBEDEVA EKATERINA Ekaterina Lebedeva obtained her double M.Sc. degree in Computational Logic at the Free University of Bolzano, Italy, and at Vienna University of Technology, Austria. She currently works as a research assistant in the Calligramme team in the Institut National de Recherche en Informatique et en Automatique in Lorraine (INRIA - Grand Est), France.