Approximation Algorithm for Minimum p Union Under a Geometric Setting
share
In a minimum p union problem (MinpU), given a hypergraph G=(V,E) and an integer p, the goal is to find a set of p hyperedges E'⊆ E such that the number of vertices covered by E' (that is |⋃_e∈ E'e|) is minimized. It was known that MinpU is at least as hard as the densest k-subgraph problem. A question is: how about the problem in some geometric settings? In this paper, we consider the unit square MinpU problem (MinpU-US) in which V is a set of points on the plane, and each hyperedge of E consists of a set of points in a unit square. A (1/1+ε,4)-bicriteria approximation algorithm is presented, that is, the algorithm finds at least p/1+ε unit squares covering at most 4opt points, where opt is the optimal value for the MinpU-US instance (the minimum number of points that can be covered by p unit squares).
READ FULL TEXT