| Title: | Faster distance-based representative skyline and k-center along pareto front in the plane |
|---|
| Authors: | ID Cabello, Sergio (Author) |
|---|
| Files: |  URL - Source URL, visit https://link.springer.com/article/10.1007/s10898-023-01280-1
 PDF - Presentation file, download (2,13 MB)
MD5: 6B274F3D80C2B0EF1B0EF7D70DB07F8A
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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$. |
|---|
| Keywords: | geometric optimization, skyline, pareto front, clustering, k-center |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.06.2023 |
|---|
| Year of publishing: | 2023 |
|---|
| Number of pages: | str. 441-466 |
|---|
| Numbering: | Vol. 86, iss. 2 |
|---|
| PID: | 20.500.12556/DiRROS-18407  |
|---|
| UDC: | 004.9:519.8 |
|---|
| ISSN on article: | 0925-5001 |
|---|
| DOI: | 10.1007/s10898-023-01280-1 |
|---|
| COBISS.SI-ID: | 145465859 |
|---|
| Note: | Spletna objava: 16. 3. 2023;
|
|---|
| Publication date in DiRROS: | 15.03.2024 |
|---|
| Views: | 551 |
|---|
| Downloads: | 257 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
