$\ell_\infty$ partially enclosing ball problem

Suppose I have $$n$$ points in $$\mathbb{R}^d$$ endowed with the $$\ell_\infty$$ metric, and I wish to find a minimum-diameter ball that contains some $$k$$ of these points. What is known about this problem? Easy/hard? Approximations? Heuristics?

• I suspect this is hard. This paper has an algorithm with running time roughly $O(k^{O(d)} n\log n)$ jeffe.cs.illinois.edu/pubs/pdf/small.pdf – Sasho Nikolov Jun 19 '19 at 15:34
• @SashoNikolov is correct. Every n-vertex graph is the intersection graph of O(n)-dimensional unit hypercubes. Thus, in sufficiently high dimensions, this problem is equivalent to deciding whether a given graph contains a k-clique. – Jeffε Jun 24 '19 at 4:37
• @Jeffε if you turn into a (sourced) answer, I'll be happy to accept! – Aryeh Jun 24 '19 at 5:25
• Although I'm also interested in various heuristics used in practice. – Aryeh Jun 24 '19 at 5:26