The UvA-LINKER will give you a range of other options to find the full text of a publication (including a direct link to the full-text if it is located on another database on the internet).
De UvA-LINKER biedt mogelijkheden om een publicatie elders te vinden (inclusief een directe link naar de publicatie online als deze beschikbaar is in een database op het internet).

Search results

Record: oai:ARNO:419938

AuthorBrammert Ottens
TitleComparing Winner Determination Algorithms for Mixed Multi-Unit Combinatorial Auctions
FacultyFaculty of Science
Institute/dept.FNWI/FGw: Institute for Logic, Language and Computation (ILLC)
SeriesILLC Master of Logic Theses / ILLC ; MoL-2007-17
AbstractComparing Winner Determination Algorithms for Mixed Multi-Unit Combinatorial Auctions
Brammert Ottens

In this thesis three different approaches to the Winner Determination
Problem (WDP) for Mixed Multi-Unit Combinatorial Auctions (MMUCA) are
explored. The first, due to [Cerquides et al., 2007] is based on a
traditional integer programming approach. The second, due to [Uckelman
and Endriss, 2007] is based on constraint programing and the third is
based on a division of the original problem in two subproblems.
These two subproblems are the problem of finding an allocation that
produces enough goods, and the problem of finding a sequence of the
transformations in this allocation. It is shown that both problems are
NP-complete. However, in the case of an acyclic goods graph the
problem of finding a sequence becomes trivial. This is also the case
when any cycles present limit themselves to just one good, i.e. the
good occurs both in the input and in the output of a transformations.
All three algorithms are tested using two different datasets. The
first is created using the generator described in [Vinyals et al.,
2007] and discerns three different types of transformations, input,
output and input-output transformations. The second is created using
a generator that discerns four different types of transformations,
namely input, output, structured and unstructured transformations.
In terms of performance the results are not conclusive. Although the
constraint programming approach does not perform very well, the
performance of both the integer programming approach and the division
approach vary. In several situations the latter is better and in other
situations the former is better. Furthermore, the influence of the
number of transformations on the complexity of the auction varies for
the different datasets.
However, the results do show that structured auctions are easier to
solve than unstructured and hybrid auctions and that the division
approach performs much better on structured auctions.
Document typePreprint
Document finderUvA-Linker