On Computing Centroids According to the $p$-Norms of Hamming Distance Vectors

In this paper we consider the $p$-Norm Hamming Centroid problem which asks to determine whether some given binary strings have a centroid with a bound on the $p$-norm of its Hamming distances to the strings. Specifically, given a set of strings $S$ and a real $k$, we consider the problem of determining whether there exists a string $s^{\ast }$ with $\big(\sum_{s \in S}d^p(s^*,s)\big)^{1/p} \leq k$,where$d(,)$ denotes the Hamming distance metric. This problem has important applications in data clustering, and is a generalization of the well-known polynomial-time solvable $\text{textsc}ConsensusString$ $(p=1)$ problem, as well as the NP-hard $\text{textsc}ClosestString$ $(p=\mathrm{\infty })$ problem. Our main result shows that the problem is NP-hard for all fixed rational $p > 1$,closingthegapforallrationalvaluesof$p$between$1$and$\infty$. Under standard complexity assumptions the reduction also implies that the problem has no $2^{o(n+m)}$-time or $2^{o(k^{\frac{p}{(p+1)}})}$-time algorithm, where $m$ denotes the number of input strings and $n$ denotes the length of each string, for any fixed $p>1$. Both running time lower bounds are tight. In particular, we provide a $2^{k^{\frac{p}{(p+1)}+\epsilon }}$-time algorithm for each fixed $\epsilon >0$. In the last part of the paper, we complement our hardness result by presenting a fixed-parameter algorithm and a factor-$2$ approximation algorithm for the problem.