Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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