Constrained Hitting Set Problem with Intervals
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00548662" target="_blank" >RIV/67985807:_____/21:00548662 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-030-89543-3_50" target="_blank" >http://dx.doi.org/10.1007/978-3-030-89543-3_50</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-89543-3_50" target="_blank" >10.1007/978-3-030-89543-3_50</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Constrained Hitting Set Problem with Intervals
Popis výsledku v původním jazyce
We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset then we must select all the points from that subset. In general, when the intervals are disjoint, we prove that the problem is in FPT, when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. Next, we consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. However, when each subset contains at most 3 points and intervals are disjoint, we prove that the problem is NP-Hard and we provide two constant factor approximations for the problem.
Název v anglickém jazyce
Constrained Hitting Set Problem with Intervals
Popis výsledku anglicky
We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset then we must select all the points from that subset. In general, when the intervals are disjoint, we prove that the problem is in FPT, when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. Next, we consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. However, when each subset contains at most 3 points and intervals are disjoint, we prove that the problem is NP-Hard and we provide two constant factor approximations for the problem.
Klasifikace
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)
Návaznosti výsledku
Projekt
<a href="/cs/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2021
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Computing and Combinatorics: 27th International Conference, COCOON 2021 Proceedings
ISBN
978-3-030-89542-6
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
13
Strana od-do
604-616
Název nakladatele
Springer
Místo vydání
Cham
Místo konání akce
Tainan
Datum konání akce
24. 10. 2021
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000767965300050