Rainbow minmax gap
Rainbow minmax gap is a problem in combinatorial optimization.
Definitions
There is a set P of n colored points on the real line.
A subset Q of P is called a rainbow set if it contains at most a single point of each color; it is called a complete rainbow set if it contains exactly one point of each color.
The max gap of a set of points Q is the largest difference between consecutive points of Q.
Rainbow minmax gap is the problem of finding a complete rainbow set Q, such that max-gap(Q) is as small as possible.
Solutions
The problem is NP-hard.[1] There is a 2-factor approximation algorithm.[2]
References
- ↑ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "Selecting and covering colored points". Discrete Applied Mathematics. 250: 75–86. doi:10.1016/j.dam.2018.05.011. ISSN 0166-218X.
- ↑ Consuegra, Mario E.; Narasimhan, Giri (2013). Seth, Anil; Vishnoi, Nisheeth K., eds. "Geometric Avatar Problems". IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 24: 389–400. doi:10.4230/LIPIcs.FSTTCS.2013.389. ISBN 978-3-939897-64-4.
This article "Rainbow minmax gap" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Rainbow minmax gap. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
