ABSTRACT
Packing and stabbing (or covering) problems are two basic problems in combinatorial optimization. Apart from the fact that they arise in many practical applications, investigating these problems improves our understanding of fundamental issues in combinatorial optimization. Admittedly, the generality of a packing or a stabbing problem has its price: When it comes to solving such a problem, and when one insists that an optimal solution is produced for all instances, one needs to accept that, for some instances, large running times are unavoidable. Moreover, when one restricts oneself to polynomial-time algorithms, only very weak statements concerning the quality of the solutions found can be made (see, e.g., Chapter 1, Ausiello et al. [1] or Vazirani [2] for an introduction and terminology).
