algorithm - 如果一个优化问题在 L1-metric 下是 NP-hard，那么对于 L2-metric 下的问题我们能说什么呢？

Question

我遇到了一些经典问题，例如 k-means 和 k-median 问题，正在研究各种指标下的不可近似性结果。我有一个一般性（也许是愚蠢的）问题。如果优化问题在 L1-metric 下是 NP-hard，那么对于 L2-metric 下的问题我们能说什么呢？类似地，如果我们知道一个优化问题在 L1-metric 下是 APX-hard，那么我们可以说这个问题在 L2-metric 下的 APX-hardness 是什么？你能澄清一下或给我一个参考/链接吗？

提前谢谢你。

标签： algorithmnp-hard