Indexed by:Conference Paper

Date of Publication:2015-12-18

Included Journals:CPCI-S、EI

Volume:9486

Page Number:794-808

Abstract: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.