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

Sergio Cabello ()
Additional contact information
Sergio Cabello: Univerza v Ljubljani Fakulteta za matematiko in fiziko

Journal of Global Optimization, 2023, vol. 86, issue 2, No 7, 466 pages

Abstract: Abstract 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)$$ 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)$$ O ( n log k ) time and the optimization problem can be solved in $$O(n \log k + n {{\,\textrm{loglog}\,}}n)$$ O ( n log k + n loglog n ) time. This improves previous algorithms and is optimal for a large range of values of k.

Keywords: Geometric optimization; Skyline; Pareto front; Clustering; k-center (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01280-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:86:y:2023:i:2:d:10.1007_s10898-023-01280-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01280-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().