Linear Time Approximation Schemes for Geometric Maximum Coverage

Abstract

We study approximation algorithms for the following geometric version of the maximum coverage problem: Let P be a set of n weighted points in the plane. We want to place m a * b rectangles such that the sum of the weights of the points in P covered by these rectangles is maximized.For any fixed > 0, we present efficient approximation schemes that can find (1-ε)-approximation to the optimal solution.In particular, for m = 1, our algorithm runs in linear time O(n log( 1/ε)), improving over the previous result. For m > 1, we present an algorithm that runs in O(n/εlog(1/ε)+m(1/ε)^(O(min(sqrt(m),1/ε))) time.

17 pages, 4 figures, to be published in the Proceedings of 21st International Computing and Combinatorics Conference(COCOON2015)