Podrobno

Searching in Euclidean spaces with predictions
ID Cabello, Sergio (Avtor), ID Giannopoulos, Panos (Avtor)

.pdfPDF - Predstavitvena datoteka, prenos (840,91 KB)
MD5: 494ED67441FCCB480C72505EA1E613D4
URLURL - Izvorni URL, za dostop obiščite https://link.springer.com/article/10.1007/s00224-026-10291-w Povezava se odpre v novem oknu

Izvleček
We study the problem of searching for a target at some unknown location in ${\mathbb R}^d$ when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distances to the target: for each point $p \in {\mathbb R}^d$ that the searcher visits, we obtain a value $\lambda (p)$ such that $|pt|\le \lambda (p) \le c\cdot |pt|$, where $c \ge 1$ is a fixed constant, $t$ is the position of the target, and $|pt|$ is the Euclidean distance of $p$ to $t$. The cost of the search is the length of the path followed by the searcher. Our main positive result is a strategy that achieves $O(c^d)$-competitive ratio, even when the constant c is unknown. We also give a lower bound of roughly $(c/4)^{d-1}$ on the competitive ratio of any search strategy in ${\mathbb R}^d$, assuming that $c\ge 4$.

Jezik:Angleški jezik
Ključne besede:search games, predictions, distance, computational geometry
Vrsta gradiva:Članek v reviji
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FMF - Fakulteta za matematiko in fiziko
Status publikacije:Objavljeno
Različica publikacije:Objavljena publikacija
Leto izida:2026
Št. strani:27 str.
Številčenje:Vol. 70, iss. 3, art. 49
PID:20.500.12556/RUL-188803 Povezava se odpre v novem oknu
UDK:004.9
ISSN pri članku:1432-4350
DOI:10.1007/s00224-026-10291-w Povezava se odpre v novem oknu
COBISS.SI-ID:292763139 Povezava se odpre v novem oknu
Datum objave v RUL:28.09.2026
Število ogledov:136
Število prenosov:34
Metapodatki:XML DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Gradivo je del revije

Naslov:Theory of computing systems
Založnik:Springer
ISSN:1432-4350
COBISS.SI-ID:13043686 Povezava se odpre v novem oknu

Licence

Licenca:CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

Jezik:Slovenski jezik
Ključne besede:igre, napovedi, računska geometrija

Projekti

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:P1-0297
Naslov:Teorija grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:J1-2452
Naslov:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0218
Naslov:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0285
Naslov:Metrični problemi v grafih in hipergrafih

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:J1-70045
Naslov:Splošna lega in vidnost v teoriji grafov

Financer:EC - European Commission
Številka projekta:101071836
Naslov:KARST: Predicting flow and transport in complex Karst systems
Akronim:KARST

Financer:EC - European Commission
Številka projekta:882971
Naslov:From Geometry to Combinatorics and Back: Escaping the Curse of Dimensionality
Akronim:GeoScape

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj