On approximability of minimum color-spanning ball in high dimensions

DOI10.1016/j.dam.2019.10.016zbMath1473.68202MaRDI QIDQ2181229

Payam Khanteimouri, Ali Mohades, Mohammad Reza Kazemi

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.10.016

zbMATH Keywords

approximation algorithm; approximability; exponential time hypothesis (ETH); color-spanning set; high-dimensional spaces

Mathematics Subject Classification ID

68P15: Database theory

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms