Bin Packing and Covering Problems with Rejection
In this paper we consider the following problems: We are given a set of n items u1, …,un, each item ui is characterized by its size wi ∈ (0,1 and its penalty/profit pi≥0, and a number of unit-capacity bins. An item can be either rejected, in which case we pay/get its penalty/profit, or put into one bin under the constraint that the total size of the items in the bin is not greater/smaller than 1.No item can be spread into more than one bin. The objective is to minimize/maximize the sum of the number of used/covered bins and the penalties/profits of all rejected items. We call the problems bin packing/covering with rejection penalties/profits, and denoted by BPR and BCR respectively. For the online BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio of arbitrarily close to 7/4 while the lower bound is 1.540.For the offline BPr problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 3/2, and an algorithm with an asymptotic worst-case ratio of 3/2.For the online BCR problem, we show that no algorithm can have an absolute competitive ratio of greater than 0, and present an algorithm with an asymptotic competitive ratio of 1/2, which is the best possible. For the offline BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound.
Yong He Gyorgy Dosa
Department of Mathematics, and State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, P.R. Department of Mathematics, University of Veszprem, Hungary
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
885-894
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）