DIKUL - logo
(UL)
  • Faster distance-based representative skyline and k-center along pareto front in the plane
    Cabello, Sergio
    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$▫.
    Source: Journal of global optimization. - ISSN 0925-5001 (Vol. 86, iss. 2, June 2023, str. 441-466)
    Type of material - article, component part ; adult, serious
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 145465859

    Link(s):

    https://link.springer.com/article/10.1007/s10898-023-01280-1
    DiRROS - Digital repository of Slovenian research organizations
    Repository of the University of Ljubljana – RUL
    DOI

source: Journal of global optimization. - ISSN 0925-5001 (Vol. 86, iss. 2, June 2023, str. 441-466)

loading ...
loading ...
loading ...

Shelf entry