Conflict-free Covering.
Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov · Canadian Conference on Computational Geometry · 2015
LetP =fC1;C2;:::;Cng be a set of color classes, where each color class Ci consists of a set of points. In this paper, we address a family of covering problems, in which one is allowed to cover at most one point from each color class. We prove that the problems in this family are NPcomplete (or NP-hard) and oer several constant-factor approximation algorithms.