Third Joint International Conference, FAW-AAIM 2013
開催地
和文:
英文:
アブストラクト
In this paper, we study removable online knapsack problem. The input is a sequence of items e 1,e 2,…,e n , each of which has a weight and a value. Given the ith item e i , we either put e i into the knapsack or reject it. When e i is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the weight of e i and the total weight in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We show a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also give a lower bound 1?+?1/e???1.368. For the unweighted case, i.e., the value of each item is equal to the weight, we propose a 10/7-competitive algorithm and give a lower bound 1.25.
各種検索
サポート
ヘルプ