点击次数：

论文类型：会议论文

发表时间：2015-12-18

收录刊物：EI、CPCI-S

卷号：9486

页面范围：794-808

摘要：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, i.e., 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, i.e., the sum of the weights of elements kept until the end minus the total cancellation cost occurred. We consider the matroid and unweighted knapsack constraints. For either case, we construct optimal online algorithms and prove that they are the best possible.