| Naslov: | Faster distance-based representative skyline and k-center along pareto front in the plane |
|---|
| Avtorji: | ID Cabello, Sergio (Avtor) |
|---|
| Datoteke: |  URL - Izvorni URL, za dostop obiščite https://link.springer.com/article/10.1007/s10898-023-01280-1
 PDF - Predstavitvena datoteka, prenos (2,13 MB)
MD5: 6B274F3D80C2B0EF1B0EF7D70DB07F8A
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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$. |
|---|
| Ključne besede: | geometric optimization, skyline, pareto front, clustering, k-center |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.06.2023 |
|---|
| Leto izida: | 2023 |
|---|
| Št. strani: | str. 441-466 |
|---|
| Številčenje: | Vol. 86, iss. 2 |
|---|
| PID: | 20.500.12556/DiRROS-18407  |
|---|
| UDK: | 004.9:519.8 |
|---|
| ISSN pri članku: | 0925-5001 |
|---|
| DOI: | 10.1007/s10898-023-01280-1 |
|---|
| COBISS.SI-ID: | 145465859 |
|---|
| Opomba: | Spletna objava: 16. 3. 2023;
|
|---|
| Datum objave v DiRROS: | 15.03.2024 |
|---|
| Število ogledov: | 558 |
|---|
| Število prenosov: | 260 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
