Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs

While capacity constraints appear naturally in many applications, the combinatorial and algorith-mic nature of capacitated covering problems remains unresolved. Only a few capacitated problems were studied including the general case of Set Cover [9] and the restricted case of Vertex Cover [2, 7, 4]. In this work we consider a capacitated version of a covering problem, called rectangle stabbing. The geometric nature of the problem is used to obtain exact algo-rithms and constant approximation ratios for some versions of the problem. The rectangle stabbing problem (rs) is a covering problem. Its uncapacitated version is defined as fol-lows. The input is a finite set U of axis parallel rec-tangles and a finite set S of horizontal and vertical lines. A cover is a subset of S that intersects every rectangle in U at least once. The goal is to find a cover of minimum size. We denote the set of rec-tangles that a line S ∈ S intersects by U(S). Using this notation, an rs instance is simply a Set Cover instance in which the goal is to find a collection of subsets of the form U(S), the union of which equals U. Without loss of generality, one may assume that the rs instance is discrete in the following sense [5]: rectangle corners have integral coordinates and lines intersect the axes at integral points. In the one-dimensional version, the set U consists of horizontal intervals and the set S consists of points. This is the well known clique cover problem in inter-val graphs that is solvable in polynomial time [6]. The rs problem can be extended to d dimensions (d-rs). For d ≥ 3, the set U consists of axis par-allel d-dimensional rectangles (i.e., “boxes”) and th