# Metric 1-Center in l-infinity norm (when dimension is part of the input)

Consider the following problem,

Input: A number $d>0$, $X \subseteq \mathbb{R}^d$.

Output: A center $c\in \mathbb{R}^d$ s.t $\max_{x \in X} \lVert x - c\rVert_p$ is minimized.

This is the 1-center problem in the metric space $(X, \ell_p)$, i.e $d$ dimensional Euclidean space equipped with $\ell_p$ norm. The problem is NP-Hard for $p=2$. Is it also NP-Hard for $p=\infty$? More generally, is it NP-Hard for any $1\leq p \leq \infty$?

• Basically, my doubt is: Does NP-Hardness not directly follow from this dl.acm.org/citation.cfm?id=62255? – Debjyoti555 Apr 12 '18 at 18:30
• The question about $p=\infty$ is not research-level. If you put a bit of thought into it you should be able to figure it out on your own. Hint: try thinking about the case $d=1$ first. Then try $d=2$. Can you generalize? The case $p=1$ is not research-level either (use linear programming). – D.W. Apr 13 '18 at 5:16