Katrin Casel, Trier
"Resolving Conflicts for Lower-Bounded Clustering"

 Abstract:

For most clustering problems, the quality of a solution is usually assessed with respect to a given pairwise distance on the input objects.

Strategies for computing (approximate) solutions for such tasks often rely on this distance to be a metric. But what happens if this property does not hold? Especially for computing a clustering such that each cluster has a certain minimum cardinality k>2 (as required for anonymization or balanced facility location problems) this becomes problematic. For example, with the objective to minimize the maximum radius of all clusters, there exists no polynomial-time constant factor approximation if the triangle inequality is violated while there exists a 2-approximation for metric distances. We try to resolve or at least soften this effect of non-metric distances by devising particular strategies to deal with violations of the triangle inequality (conflicts). With the use of parameterized algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently.