On the k-colored Rainbow Sets in Fixed Dimensions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00550972" target="_blank" >RIV/67985807:_____/21:00550972 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-030-92681-6_46" target="_blank" >http://dx.doi.org/10.1007/978-3-030-92681-6_46</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-92681-6_46" target="_blank" >10.1007/978-3-030-92681-6_46</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the k-colored Rainbow Sets in Fixed Dimensions

Popis výsledku v původním jazyce

In this paper, we introduce a variant of the minimum diameter color spanning set (MDCSS) problem. Let P be a set of n points of m colors in Rd . For a given k, our objective is to find a set with k points of different colors that admits the minimum possible diameter. Such a set is called a k-rainbow set. This problem has applications in database queries, mostly composed by weighted points (i.e., a positive value is assigned to each point as its weight), and seeking a maximum weight k-rainbow set. We first assume the points have equal weight and design an FPT algorithm, which we generalize to the weighted version. We also solve the decision and the enumeration version of the problem by introducing a reduction to all maximal independent sets of a bipartite graph. We also introduce a 1.154-approximation algorithm for this problem and a 2.236-approximation for the enumeration version, and we perform some experimental studies on a real data-set, as well as providing several analyses of the data-set based on the outputs of our algorithm. Our exact algorithms and the approximation algorithm for the enumeration problem have a complexity being near-linear to n in R2 .

Název v anglickém jazyce

On the k-colored Rainbow Sets in Fixed Dimensions

Popis výsledku anglicky

In this paper, we introduce a variant of the minimum diameter color spanning set (MDCSS) problem. Let P be a set of n points of m colors in Rd . For a given k, our objective is to find a set with k points of different colors that admits the minimum possible diameter. Such a set is called a k-rainbow set. This problem has applications in database queries, mostly composed by weighted points (i.e., a positive value is assigned to each point as its weight), and seeking a maximum weight k-rainbow set. We first assume the points have equal weight and design an FPT algorithm, which we generalize to the weighted version. We also solve the decision and the enumeration version of the problem by introducing a reduction to all maximal independent sets of a bipartite graph. We also introduce a 1.154-approximation algorithm for this problem and a 2.236-approximation for the enumeration version, and we perform some experimental studies on a real data-set, as well as providing several analyses of the data-set based on the outputs of our algorithm. Our exact algorithms and the approximation algorithm for the enumeration problem have a complexity being near-linear to n in R2 .

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/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

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ů

Název statě ve sborníku

Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings

ISBN

978-3-030-92680-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

587-601

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Tianjin

Datum konání akce

17. 12. 2021

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

WRD - Celosvětová akce

Kód UT WoS článku

—