数学科学系

Department of Mathematical Sciences

Randomized Algorithms for Removable Online Knapsack Problems

报告题目Randomized Algorithms for Removable Online Knapsack Problems

 

报告人:韩鑫副教授(大连理工大学)

 

时间2013510号(星期五)16:00-17:00

 

地点:理科楼数学系A304

 

摘要In this paper, we study removable online knapsack problem. The input is a sequence of items e_1,e_2,\dots,e_n, each of which has a weight and a value. Given the i-th 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 \approx 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.

 

联系人:王振波