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$?

  • $\begingroup$ Basically, my doubt is: Does NP-Hardness not directly follow from this dl.acm.org/citation.cfm?id=62255? $\endgroup$ – Debjyoti555 Apr 12 '18 at 18:30
  • $\begingroup$ 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). $\endgroup$ – D.W. Apr 13 '18 at 5:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.