Chen, Jiehua ;
Hermelin, Danny ;
Sorge, Manuel
On Computing Centroids According to the pNorms of Hamming Distance Vectors
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}
}
06.09.2019
Keywords: 

Strings, Clustering, Multiwinner Election, Hamming Distance 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 