科研之友
微信
新浪微博
Facebook
分享链接
摘要
The capacitated unit covering problem is a generalization of the bin packing and the unit covering problems. In its one-dimensional case, there are n weighted points on a line and we want to partition them into a minimum number of sets such that (i) the total weight of points in each set is no more than one and (ii) the points in each set can be covered by a unit-length interval. The problem is not approximable within a factor better than 1.5 unless P=NP. We analyse a generalization of the first-fit algorithm for this problem, which runs in O (n log n) time, and prove that when no point has weight more than its approximation ratio is exactly 5/3 approximate to 1.667.
- 出版日期2017-7
