首页    期刊浏览 2024年09月01日 星期日
登录注册

文章基本信息

  • 标题:SEPARABLE CONVEX RESOURCE ALLOCATION PROBLEM WITH L1-DISTANCE CONSTRAINT
  • 本地全文:下载
  • 作者:Norito Minamikawa ; Akiyoshi Shioura
  • 期刊名称:日本オペレーションズ・リサーチ学会論文誌
  • 印刷版ISSN:0453-4514
  • 电子版ISSN:2188-8299
  • 出版年度:2019
  • 卷号:62
  • 期号:3
  • 页码:109-120
  • DOI:10.15807/jorsj.62.109
  • 出版社:Japan Science and Technology Information Aggregator, Electronic
  • 摘要:

    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 1-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 1-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.

  • 关键词:Discrete optimization;resource allocation problem;separable convex function;polymatroid constraint
国家哲学社会科学文献中心版权所有