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

Cabello, Sergio (author)

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$.

• Language: English
• Keywords: geometric optimization, skyline, pareto front, clustering, k-center
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2023
• Number of pages: Str. 441-466
• Numbering: Vol. 86, iss. 2
• PID: 20.500.12556/RUL-147583
• UDC: 004.9:519.8
• ISSN on article: 0925-5001
• DOI: 10.1007/s10898-023-01280-1
• COBISS.SI-ID: 145465859
• Publication date in RUL: 07.07.2023

Record is a part of a journal

• Title: Journal of global optimization
• Shortened title: J. glob. optim.
• Publisher: Springer Nature
• ISSN: 0925-5001
• COBISS.SI-ID: 2822695

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.