In this paper, we study unit cost buyback problem, i.e., the buyback problem with fixed cancellation cost for each cancelled item. 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. In order to accept a new element e i , we could cancel some previous selected elements at a cost which is proportional to the number of elements canceled. Our goal is to maximize the profit, i.e., the sum of the 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.
各種検索
サポート
ヘルプ