On the k-colored Rainbow Sets in Fixed Dimensions

Authors: Vahideh Keikha, H. Keikha, A. Mohades
Publication year: 2021
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings
Projects: Structural properties of visibility in terrains and farthest color Voronoi diagrams
Bibliographic citation: KEIKHA, Vahideh, KEIKHA, H., MOHADES, A. On the k-colored Rainbow Sets in Fixed Dimensions. In: DU, D.-Z., DU, D., WU, Ch., XU, D., eds. Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings. Cham: Springer, 2021, S. 587-601. Lecture Notes in Computer Science, 13135. ISBN 978-3-030-92680-9. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-030-92681-6_46
DOI: 10.1007/978-3-030-92681-6_46
ID: 550972

Abstract

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 .