Abstract
In this paper we consider the pNorm Hamming Centroid problem which asks to determine whether some given strings have a centroid with a bound on the pnorm of its Hamming distances to the strings. Specifically, given a set S of strings and a real k, we consider the problem of determining whether there exists a string s^* with (sum_{s in S} d^{p}(s^*,s))^(1/p) <=k, where d(,) denotes the Hamming distance metric. This problem has important applications in data clustering and multiwinner committee elections, and is a generalization of the wellknown polynomialtime solvable Consensus String (p=1) problem, as well as the NPhard Closest String (p=infty) problem.
Our main result shows that the problem is NPhard 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 the problem has no 2^o(n+m)time or 2^o(k^(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. The first bound matches a straightforward bruteforce algorithm. The second bound is tight in the sense that for each fixed epsilon > 0, we provide a 2^(k^(p/((p+1))+epsilon))time algorithm. In the last part of the paper, we complement our hardness result by presenting a fixedparameter algorithm and a factor2 approximation algorithm for the problem.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2019:11149,
author = {Jiehua Chen and Danny Hermelin and Manuel Sorge},
title = {{On Computing Centroids According to the pNorms of Hamming Distance Vectors}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {28:128:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11149},
URN = {urn:nbn:de:0030drops111495},
doi = {10.4230/LIPIcs.ESA.2019.28},
annote = {Keywords: Strings, Clustering, Multiwinner Election, Hamming Distance}
}
Keywords: 

Strings, Clustering, Multiwinner Election, Hamming Distance 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 