The Line-Constrained Maximum Coverage Facility Location Problem

We consider the maximum coverage facility location problem in the plane. In this paper, we restrict the facilities to be located on the given line, and propose an \(O(n^2)\) algorithm for this problem by transforming the problem to the maximum weight k-link path problem in a complete directed acyclic graph, and by proving the concave Monge property inherent to the edge weights of the graph by which the substantial improvement of the running time compared with the straightforward implementation is attained.