SEPARABLE CONVEX RESOURCE ALLOCATION PROBLEM WITH L1-DISTANCE CONSTRAINT

• Minamikawa Norito

  Tokyo Institute of Technology

• Shioura Akiyoshi

  Tokyo Institute of Technology

抄録

Separable convex resource allocation problem aims at finding an allocation of a discrete resource to several activities that minimizes a separable convex function representing the total cost or the total loss. In this paper, we consider the separable convex resource allocation problem with an additional constraint that the L₁-distance between a given vector and a feasible solution is bounded by a given positive constant. We prove that the simplest separable convex resource allocation problem with the L₁-distance constraint can be reformulated as a submodular resource allocation problem. This result implies that the problem can be solved in polynomial time by existing algorithms for the submodular resource allocation problem. We present specialized implementations of the existing algorithms and analyze their running time.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 62 (3), 109-120, 2019-07-31

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Discrete optimization
• resource allocation problem
• separable convex function
• polymatroid constraint

詳細情報

• CRID: 1390282763132269952
• NII論文ID: 130007685316
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.62.109
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 029860191
• Web Site: http://id.ndl.go.jp/bib/029860191
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I029860191
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/62/3/62_109/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可