Analysis of a first-fit algorithm for the capacitated unit covering problem

ABSTRACT

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 $\frac{1}{2}$, its approximation ratio is exactly $\frac{5}{3}$ ≈ 1.667.

KEYWORDS:

• Capacitated unit covering problem
• bin packing
• approximation algorithm
• computational geometry

2010 AMS SUBJECT CLASSIFICATIONS:

• 90C27
• 90C59
• 68W25
• 68W40

Acknowledgement

We thank referees for their helpful comments, which improved the paper structure and content.

Additional information

Funding

The authors also thank ‘Institute for Research in Fundamental sciences’ (IPM) for their support of this project. This research was in part supported by a grant from IPM [number CS1391-4-16].