Abstract
This paper considers the effect of nonmetric distances for lowerbounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lowerbounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomialtime constant factor approximation is possible, unless P=NP. We try to resolve or at least soften this effect of nonmetric distances by devising particular strategies to deal with violations of the triangle inequality (conflicts). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently.
In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the conflict graph (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT=W[2]. We further discuss improvements for diameter by choosing the (induced) P_3cover number of the conflict graph as parameter and complement these by showing that, unless FPT=W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.
BibTeX  Entry
@InProceedings{casel:LIPIcs:2019:10224,
author = {Katrin Casel},
title = {{Resolving Conflicts for LowerBounded Clustering}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {23:123:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10224},
URN = {urn:nbn:de:0030drops102247},
doi = {10.4230/LIPIcs.IPEC.2018.23},
annote = {Keywords: clustering, triangle inequality, parameterised approximation}
}
Keywords: 

clustering, triangle inequality, parameterised approximation 
Collection: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018) 
Issue Date: 

2019 
Date of publication: 

05.02.2019 