Proportional Cost Buyback Problem with Weight Bounds
Proportional Cost Buyback Problem with Weight Bounds
复制标题
DOI：
10.1007/978-3-319-26626-8_59
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Yasushi Kawase;Xin Han;K. Makino
中科院分区：
文献类型：
--
作者：
Yasushi Kawase;Xin Han;K. Makino
本文研究了比例成本回购问题。输入是元素e1，e2，.，en n的序列，每个元素具有权重w（e i）。我们假设权有一个上界和一个下界，即对于任何i，l≤ w（e i）≤ u。给定第i个元素e i，我们要么接受e i，要么拒绝它而不付出代价，这取决于接受元素的集合上的某些约束。在迭代过程中，我们可以取消一些先前接受的元素，其代价与它们的总权重成正比。我们的目标是利润最大化，即保留到最后的元素的权重之和减去发生的总取消成本。我们考虑一个拟阵和未加权的背包约束。对于任何一种情况下，我们构造最优的在线算法，并证明他们是最好的可能。
In this paper, we study the proportional cost buyback problem. The input is a sequence of elements e 1, e 2,…, e n, each of which has a weight w (e i). We assume that weights have an upper and a lower bound, ie, l≤ w (e i)≤ u for any i. Given the ith element e i, we either accept e i or reject it with no cost, subject to some constraint on the set of accepted elements. During the iterations, we could cancel some previously accepted elements at a cost that is proportional to the total weight of them. Our goal is to maximize the profit, ie, the sum of the weights of elements kept until the end minus the total cancellation cost occurred. We consider a matroid and the unweighted knapsack constraints. For either case, we construct optimal online algorithms and prove that they are the best possible.