Study On Online Knapsack Problem With Removal Cost

Knapsack problem is one of the classic problems about computer theory and operational research. It can apply in our real life such as industrial production, transportation and so on. What’s more, with the development of the network, Keyword Auction and display advertising have attracted extensive attention of many researchers. Since the online knapsack problem with removal cost plays an important role in Keyword Auction, there is very important practical value during the research of online knapsack problem.Combined with the practical application and relied on the project of online knapsack problem this paper extend the model of online knapsack problem. In this paper we put forward the online knapsack problem with removal cost and conduct some research. The online knapsack problem with removal cost means that if we remove the items selected in the knapsack for the sake of more profit the algorithm should pay some cost. In this paper we regard the value of an item as the size of it, so the profit of an online algorithm is the sum of the sizes in the knapsack minus the total removal cost occurred. We propose and study two models of the removal cost model, the proportional cost model and the unit cost model. In the proportional cost model, the removal cost of each item is proportional to its size, namely, f(f>0). According to the f we prove the lower bound of the proportional cost model. After prove that lower bound, we proposal an optional online algorithm. In the unit cost model, the removal cost of each item is constant, namely, c(c>0). According to the different values of c we prove the lower bound of this model. After prove that lower bound, we proposal an optional online algorithm.