The p-cover problem (Q1079475)

The p-cover problem deals with covering the most buying power with p new facilities. Each facility covers an area of a certain shape and size. When distances are rectilinear then the area covered by a facility has a shape of a diamond (a square rotated by \(45^ o)\). It is suggested to rotate the area by \(45^ o\), and thus each facility covers a square parallel to the axes. The data about the buying power is therefore given as a matrix where every entry in the matrix represents one basic square in a grid. Each facility covers a square that consists of k by k basic squares. K is determined by the size of the area of influence of the facility and the size of the basic square. The 1-cover problem is converted to selecting the k by k submatrix with the maximal sum of entries. If the area of influence is a rectangle of m by n basic squares, the problem is solved in o(mn) time. The p-cover problem for \(p>1\) is also discussed.