Computing Largest Minimum Color-Spanning Intervals of Imprecise Points

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00375488" target="_blank" >RIV/68407700:21240/24:00375488 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-55598-5_6" target="_blank" >https://doi.org/10.1007/978-3-031-55598-5_6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-55598-5_6" target="_blank" >10.1007/978-3-031-55598-5_6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computing Largest Minimum Color-Spanning Intervals of Imprecise Points

Popis výsledku v původním jazyce

We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in O(n^2 log n) time when k=2, by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.

Název v anglickém jazyce

Computing Largest Minimum Color-Spanning Intervals of Imprecise Points

Popis výsledku anglicky

We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in O(n^2 log n) time when k=2, by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GX23-04949X" target="_blank" >GX23-04949X: Stěžejní otázky diskrétní geometrie</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

16th Latin American Theoretical Informatics Symposium (LATIN 2024)

ISBN

978-3-031-55598-5

ISSN

1611-3349

e-ISSN

1611-3349

Počet stran výsledku

16

Strana od-do

81-96

Název nakladatele

Springer, Cham

Místo vydání

—

Místo konání akce

Puerto Varas

Datum konání akce

18. 3. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001214186800006