Approximation algorithms for a winner determination problem of single-item multi-unit auctions

• Takahashi Satoshi

  Graduate School of System and Information Systems, University of Tsukuba

• Shigeno Maiko

  Graduate School of System and Information Systems, University of Tsukuba

抄録

This paper treats a winner determination problem of a Vickrey-Clarke-Groves mechanism based single-item multi-unit auction. For this problem, two simple 2-approximation algorithms are proposed. One is a linear time algorithm using a linear knapsack problem. The other is a greedy type algorithm. In addition, a fully polynomial time approximation algorithm based on a dynamic programming is described. Computational experiments verify availabilities of our algorithms by comparing computational times and approximation ratios.

収録刊行物

• JSIAM Letters

  JSIAM Letters 3 (0), 29-32, 2011

  一般社団法人 日本応用数理学会

キーワード

• auction theory
• winner determination
• approximation algorithm

詳細情報

• CRID: 1390001205301515904
• NII論文ID: 130000674185
• DOI: 10.14495/jsiaml.3.29
• ISSN: 18830617
• ISSN: 18830609
• Web Site: https://www.jstage.jst.go.jp/article/jsiaml/3/0/3_0_29/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可