Given a set B of d-dimensional boxes (i.e., axis-aligned hyperrectangles), a
minimum coverage kernel is a subset of B of minimum size covering the same
region as B. Computing it is NP-hard, but as for many similar NP-hard problems
(e.g., Box Cover, and Orthogonal Polygon Covering), the problem becomes
solvable in polynomial time under restrictions on B. We show that computing
minimum coverage kernels remains NP-hard even when restricting the graph
induced by the input to a highly constrained class of graphs. Alternatively, we
present two polynomial-time approximation algorithms for this problem: one
deterministic with an approximation ratio within O(log n) and one randomized
with an improved approximation ratio within O(lg OPT (with high probability).