Search this article in Google Scholar

分類 論文誌
著者名 (author) Masaya Mito,Satoshi Fujita
英文著者名 (author)
キー (key)
表題 (title) On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions
表題 (英文)
定期刊行物名 (journal) Journal of Heuristics
定期刊行物名 (英文)
巻数 (volume) 10
号数 (number) 5
ページ範囲 (pages) 507-523
刊行月 (month) September
出版年 (year) 2004
付加情報 (note)
注釈 (annote)
内容梗概 (abstract) The winner determination problem (WDP) in combinatorial auctions is the problem of, given a finite set of combinatorial bids B, finding a feasible subset B of B with a maximum revenue. WDP is known to be equivalent to the maximum weight set packing problem, and hard to approximate by polynomial time algorithms. This paper proposes three heuristic bid ordering schemes for solving WDP; the first two schemes take into account the number of goods shared by conflicting bids, and the third one is based on a recursive application of such local heuristic functions. We conducted several experiments to evaluate the goodness of the proposed schemes. The result of experiments implies that the first two schemes are particularly effective to improve the performance of the resulting heuristic search procedures. More concretely, they are scalable compared with the conventional linear programming (LP) relaxation based schemes, and could quickly provide an optimum solution under optimization schemes such as the branch-and-bound method. In addition, they exhibit a good anytime performance competitive to the LP-based schemes, although it is sensitive to configurable parameters controlling the strength of contributions of bid conflicts to the resultant bid ordering schemes.
論文電子ファイル Not available.

[0-6]  Masaya Mito and Satoshi Fujita, ``On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions,'' Journal of Heuristics, vol. 10, no. 5, pp. 507-523, September 2004.

    author = {Masaya Mito and Satoshi Fujita},
    author_e = {},
    title = {On Heuristics for Solving Winner Determination Problem in
    Combinatorial Auctions},
    title_e = {},
    journal = {Journal of Heuristics},
    journal_e = {},
    volume = {10},
    number = {5},
    pages = {507-523},
    month = {September},
    year = {2004},
    note = {},
    annote = {}

This site is maintained by Distributed System Laboratory.

PMAN 2.5.5 - Paper MANagement system / (C) 2002-2008, Osamu Mizuno / All rights reserved.