1.
Faster distance-based representative skyline and k-center along pareto front in the planeSergio Cabello, 2023, izvirni znanstveni članek
Povzetek: We consider the problem of computing the distance-based representative skyline in the plane, a problem introduced by Tao, Ding, Lin and Pei and independently considered by Dupin, Nielsen and Talbi in the context of multi-objective optimization. Given a set $P$ of $n$ points in the plane and a parameter $k$, the task is to select $k$ points of the skyline defined by $P$ (also known as Pareto front for $P$) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $O(n \log h)$ time, where $h$ is the number of points in the skyline of $P$. We also show that the decision problem can be solved in $O(n \log k)$ time and the optimization problem can be solved in $O(n \log k + n \log\log n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$.
Ključne besede: geometric optimization, skyline, pareto front, clustering, k-center
Objavljeno v DiRROS: 15.03.2024; Ogledov: 83; Prenosov: 41
Celotno besedilo (2,13 MB)
Gradivo ima več datotek! Več...
