OPTIMAL ALLOCATION PROBLEM WITH QUADRATIC UTILITY FUNCTIONS AND ITS RELATIONSHIP WITH GRAPH CUT PROBLEM

• Shioura Akiyoshi

  Tohoku University

• Suzuki Shunya

  Tohoku University

Abstract

We discuss the optimal allocation problem in combinatorial auctions, where the items are allocated to bidders so that the sum of the bidders' utilities is maximized. In this paper, we consider the case where utility functions are given by quadratic functions; the class of such utility functions has a succinct representation but is sufficiently general. The main aim of this paper is to show the computational complexity of the optimal allocation problem with quadratic utility functions. We consider the cases where utility functions are submodular and supermodular, and show NP-hardness and/or polynomial-time exact/approximation algorithms. These results are given by using the relationship with graph cut problems such as the min/max cut problem and the multiway cut problem.

Journal

• Journal of the Operations Research Society of Japan

  Journal of the Operations Research Society of Japan 55 (1), 92-105, 2012

  The Operations Research Society of Japan

Keywords

• Combinatorial optimization
• allocation problem
• submodular function
• supermodular function
• combinatorial auction
• graph cut

Details

• CRID: 1390001204109861120
• NII Article ID: 110009436529
• NII Book ID: AA00703935
• DOI: 10.15807/jorsj.55.92
• ISSN: 21888299
• ISSN: 04534514
• NDL BIB ID: 023545383
• Web Site: http://id.ndl.go.jp/bib/023545383
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I023545383
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/55/1/55_KJ00008017547/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed