Let P be a set of n weighted points, Q be a set of m unweighted points in the plane, and k a non-negative integer. We study the k-maxDominance problem, where the objective is to find a subset \(Q'\subseteq Q\) with size at most k such that the sum of the weights of the points in P dominated by at least one point in \(Q'\) is maximized. A point q in the plane dominates another point p if and only if \(x(q)\ge x(p)\) and \(y(q)\ge y(p)\) , and at least one inequality is strict. An algorithm for the k-maxDominance problem can be used to solve problems previously examined in scheduling, graph optimization, and database systems. We present a simple algorithm solving the problem in \(O(km^2+n\log m)\) time and \(O(n+m)\) space. The algorithm is faster than the existing one when \(m= o(\sqrt{n})\) . Additionally, we provide another solution to the problem with \(O(k\min \{n+m, \frac{n}{k}+m^2\}\log m)\) time and \(O(n + m)\) space. These bounds are the same or better than those of the existing solution (the bounds are better when \(m= o(\sqrt{n})\) ). The expected number of skyline points is \(\theta (\log n)\) , a term much less than \(\sqrt{n}\) . To obtain the second solution, we design a general technique that can be used to reduce the number of points n in P to \(\min \{n, m^2\}\) in any algorithm for the k-maxDominance problem.

Maximizing Weighted Dominance in the Plane

会议论文
发表日期：

2025年

查看全文

Waseem Akram,
Sanjeev Saxena

摘要

Let P be a set of n weighted points, Q be a set of m unweighted points in the plane, and k a non-negative integer. We study the k-maxDominance problem, where the objective is to find a subset \(Q'\subseteq Q\) with size at most k such that the sum of the weights of the points in P dominated by at least one point in \(Q'\) is maximized. A point q in the plane dominates another point p if and only if \(x(q)\ge x(p)\) and \(y(q)\ge y(p)\) , and at least one inequality is strict. An algorithm for the k-maxDominance problem can be used to solve problems previously examined in scheduling, graph optimization, and database systems. We present a simple algorithm solving the problem in \(O(km^2+n\log m)\) time and \(O(n+m)\) space. The algorithm is faster than the existing one when \(m= o(\sqrt{n})\) . Additionally, we provide another solution to the problem with \(O(k\min \{n+m, \frac{n}{k}+m^2\}\log m)\) time and \(O(n + m)\) space. These bounds are the same or better than those of the existing solution (the bounds are better when \(m= o(\sqrt{n})\) ). The expected number of skyline points is \(\theta (\log n)\) , a term much less than \(\sqrt{n}\) . To obtain the second solution, we design a general technique that can be used to reduce the number of points n in P to \(\min \{n, m^2\}\) in any algorithm for the k-maxDominance problem.