Approximation algorithms for geometric conflict free covering problems

摘要

In the GEOMETRIC CONFLICT FREE COVERING, we are given a set of points P, a set of closed geometric objects O and a conflict graph CG(O) with O as vertex set. An edge (O-i,O-j) in CG(O) denotes conflict between O-i and O-j and at most one among these can be part of any feasible solution. A set of objects is conflict free if they form an independent set in CG(O). The objective is to find a conflict free set of objects that maximizes the number of points covered.