In the maximizing range sum (MaxRS) problem, given (ⅰ) a set P of 2D points each of which is associated with a positive weight, and (ⅱ) a rectangle γ of specific extents, we need to decide where to place γ in order to maximize the covered weight of γ - that is, the total weight of the data points covered by γ. Algorithms solving the problem exactly entail expensive CPU or I/O cost. In practice, exact answers are often not compulsory in a MaxRS application, where slight imprecision can often be comfortably tolerated, provided that approximate answers can be computed considerably faster. Motivated by this, the present paper studies the (1 - ∈)-approximate MaxRS problem, which admits the same inputs as MaxRS, but aims instead to return a rectangle whose covered weight is at least (1 - ∈)m~*, where m~* is the optimal covered weight, and ∈ can be an arbitrarily small constant between 0 and 1. We present fast algorithms that settle this problem with strong theoretical guarantees.
展开▼
