On approximability of minimum color-spanning ball in high dimensions (Q2181229)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On approximability of minimum color-spanning ball in high dimensions |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On approximability of minimum color-spanning ball in high dimensions |
scientific article |
Statements
On approximability of minimum color-spanning ball in high dimensions (English)
0 references
18 May 2020
0 references
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.
0 references
approximation algorithm
0 references
approximability
0 references
color-spanning set
0 references
high-dimensional spaces
0 references
exponential time hypothesis (ETH)
0 references