Год издания: 2008
Количество страниц: 80
В продаже с 18.01.2012
Как только книга Hypertree Decompositions for Combinatorial Auctions: Optimal Winner Determination станет доступна для заказа в одном из интернет-магазинов, Вам на e-mail будет отправлено уведомление.Укажите e-mail для связи:
Combinatorial auctions are auctions in which each bidcan be placed on a set of items, as opposed tostandard auctions, in which each bid is placed on asingle item. The winner determination problem for combinatorial auctions is known to be NP-complete.One of the approaches to cope with the hardness ofthe problem is to identify tractable classes of combinatorial auctions by means of hypertreedecompositions. The winner determination problem istractable on the class of instances withcorresponding dual hypergraphs having hypertree widthbounded by a fixed natural number. This bookdescribes an optimal algorithm, calledComputeSetPackingK, for solving the winnerdetermination problem based on these ideas. Thealgorithm was implemented, and experimental resultsare also presented.