Faster distance-based representative skyline and k-center along pareto front in the plane

Cabello, Sergio (avtor)

We consider the problem of computing the distance-based representative skyline in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Mathematics; Optimization and Learning - Third International Conference, OLA 2020] 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$.

• Jezik: Angleški jezik
• Ključne besede: geometric optimization, skyline, pareto front, clustering, k-center
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2023
• Št. strani: Str. 441-466
• Številčenje: Vol. 86, iss. 2
• PID: 20.500.12556/RUL-147583
• UDK: 004.9:519.8
• ISSN pri članku: 0925-5001
• DOI: 10.1007/s10898-023-01280-1
• COBISS.SI-ID: 145465859
• Datum objave v RUL: 07.07.2023

Gradivo je del revije

• Naslov: Journal of global optimization
• Skrajšan naslov: J. glob. optim.
• Založnik: Springer Nature
• ISSN: 0925-5001
• COBISS.SI-ID: 2822695

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.