English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we consider the $p$-Norm Hamming Centroid problem which asks todetermine 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 ofstrings $S$ and a real $k$, we consider the problem of determining whetherthere exists a string $s^*$ with $\big(\sum_{s \in S}d^p(s^*,s)\big)^{1/p} \leqk$, where $d(,)$ denotes the Hamming distance metric. This problem hasimportant applications in data clustering, and is a generalization of thewell-known polynomial-time solvable \textsc{Consensus String} $(p=1)$ problem,as well as the NP-hard \textsc{Closest String} $(p=\infty)$ problem.  Our main result shows that the problem is NP-hard for all fixed rational $p >1$, closing the gap for all rational values of $p$ between $1$ and $\infty$.Under standard complexity assumptions the reduction also implies that theproblem has no $2^{o(n+m)}$-time or $2^{o(k^{\frac{p}{(p+1)}})}$-timealgorithm, where $m$ denotes the number of input strings and $n$ denotes thelength of each string, for any fixed $p > 1$. Both running time lower boundsare tight. In particular, we provide a$2^{k^{\frac{p}{(p+1)}+\varepsilon}}$-time algorithm for each fixed$\varepsilon > 0$. In the last part of the paper, we complement our hardnessresult by presenting a fixed-parameter algorithm and a factor-$2$ approximationalgorithm for the problem.

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