Unit Cost Buyback Problem
Unit Cost Buyback Problem
复制标题
单位成本回购问题
DOI：
10.1007/s00224-018-9897-7
复制
发表时间：
2018-11
影响因子：
0.5
通讯作者：
Makino Kazuhisa
中科院分区：
文献类型：
--
作者：
Kawase Yasushi;Han Xin;Makino Kazuhisa
在本文中，我们研究了单位成本回购问题，即，每个被取消元素的回购问题具有固定的取消成本。该问题的输入是元素E1，E2，。 。 。 ，每个元素EI具有重量W（EI）。我们一个
In this paper, we study theunit cost buyback problem, i.e., the buyback problem with a fixed cancellation cost for each canceled element. The input of the problem is a sequence of elementse1,e2, . . . ,enwhere each elementeihas a weightw(ei). We assume that the weights are in a known range [l,u], i.e.,l≤w(ei) ≤ufor anyi. Given theith elementei, we either accepteior reject it with no cost, where we can keep a set of elements that satisfies a certain constraint. In order to accept a new elementei, we can cancel some previously selected elements at a cost which is proportional to the number of elements canceled. Our goal is to maximize the profit, i.e., the total weights of elements accepted (and not canceled) minus the total cancellation cost occurred. We construct optimal online algorithms and prove that they are the best possible when the constraint is a matroid constraint or the unweighted knapsack constraint.
登录
查看更多内容
DOI：
10.1016/j.disopt.2017.07.002
发表时间：
2015-09
期刊：
--
影响因子：
--
作者：
Shun Fukuda;A. Shioura;T. Tokuyama
通讯作者：
Shun Fukuda;A. Shioura;T. Tokuyama
DOI：
10.1007/978-3-540-74208-1_13
发表时间：
2007-08
期刊：
--
影响因子：
--
作者：
K. Iwama;Guochuan Zhang
通讯作者：
K. Iwama;Guochuan Zhang
DOI：
10.1109/ispan.2005.19
发表时间：
2005-12
期刊：
8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05)
影响因子：
--
作者：
J. Noga;Veerawan Sarbua
通讯作者：
J. Noga;Veerawan Sarbua
DOI：
10.1007/978-3-319-26626-8_59
发表时间：
2015-12
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Yasushi Kawase;Xin Han;K. Makino
通讯作者：
Yasushi Kawase;Xin Han;K. Makino
DOI：
10.1137/1.9781611973068.137
发表时间：
2009-01
期刊：
--
影响因子：
--
作者：
Florin Constantin;J. Feldman;S. Muthukrishnan;Martin Pál
通讯作者：
Florin Constantin;J. Feldman;S. Muthukrishnan;Martin Pál