Computing Largest Minimum Color-Spanning Intervals of Imprecise Points

0585146 - ÚI 2025 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Acharyya, A. - Keikha, Vahideh - Saumell, M. - Silveira, R.I.
Computing Largest Minimum Color-Spanning Intervals of Imprecise Points.
LATIN 2024: Theoretical Informatics. Proceedings, part I. Cham: Springer, 2024 - (Soto, J.; Wiese, A.), s. 81-96. Lecture Notes in Computer Science, 14578. ISBN 978-3-031-55597-8.
[LATIN 2024: The Latin American Symposium /16./. Puerto Varas (CL), 18.03.2024-22.03.2024]
Klíčová slova: Color-spanning interval * Imprecise points * Algorithms
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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 (n2 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.
Trvalý link: https://hdl.handle.net/11104/0352881