  Bereg et al. (2012) introduced the Boxes Class Cover problem, which has its
roots in classification and clustering applications: Given a set of n points in
the plane, each colored red or blue, find the smallest cardinality set of
axis-aligned boxes whose union covers the red points without covering any blue
point. In this paper we give an alternative proof of APX-hardness for this
problem, which also yields an explicit lower bound on its approximability. Our
proof also directly applies when restricted to sets of points in general
position and to the case where so-called half-strips are considered instead of
boxes, which is a new result.
  We also introduce a symmetric variant of this problem, which we call
Simultaneous Boxes Class Cover and can be stated as follows: Given a set S of n
points in the plane, each colored red or blue, find the smallest cardinality
set of axis-aligned boxes which together cover S such that all boxes cover only
points of the same color and no box covering a red point intersects a box
covering a blue point. We show that this problem is also APX-hard and give a
polynomial-time constant-factor approximation algorithm.
