On approximability of minimum color-spanning ball in high dimensions (Q2181229)

Consider the $d$-dimensional Euclidean space with a given set $P$ of $n$ colored points. A color-spanning ball is a ball that contains at least one point of each color. The minimum color-spanning ball problem (MCSBP) is the question to find among the set of color-spanning balls one with minimum radius. There are interesting applications in database analysis where $P$ corresponds to keywords in the database. The question is how to find the closest $m$ keyword tuple that matches a user's query. MCSBP is NP-hard, even in two dimensions, but there exist PTASs for low dimensions. The situation is different in high dimensions. The authors prove a lower bound for any approximation scheme in high-dimensional space and an upper time bound. The proof is based on the assumption that there is no algorithm with running time of $2^{o(n)}$ for the 3-SAT where $n$ is the number of variables.