文章基本信息

标题：APPROXIMATION ALGORITHMS FOR A GENERALIZATION OF THE MAXIMUM BUDGET ALLOCATION
本地全文：下载
作者：Takuro Fukunaga
期刊名称：日本オペレーションズ・リサーチ学会論文誌
印刷版ISSN：0453-4514
电子版ISSN：2188-8299
出版年度：2021
卷号：64
期号：1
页码：31-44
DOI：10.15807/jorsj.64.31
出版社：Japan Science and Technology Information Aggregator, Electronic
摘要：The maximum budget allocation (MBA) problem is the problem of allocating items to agents so as to maximize the total payment from all agents, where the payment from an agent is the sum of prices of the items allocated to that agent, capped by the agent's budget. In this study, we consider a generalization of the MBA problem in which each item has a capacity constraint, and present two approximation algorithms for it. The first is a polynomial bicriteria algorithm that is guaranteed to output an allocation producing at least 1−r times the optimal feasible total payment, where r is the maximum ratio of price to budget, and to violate the capacity constraints on items by at most a factor of 2. The other is a pseudo-polynomial algorithm with approximation ratio 1/3·(1−r/4) that always outputs a feasible allocation.
关键词：Combinatorial optimization;budget allocation problem;knapsack problem;LP-rounding algorithm