Lower-Bounded Clustering - Models, Complexity and (Parameterised) Approximation

Lower-Bounded Clustering - Modelle, Komplexität and (Parametrisierte) Approximation

  • This thesis considers the general task of computing a partition of a set of given objects such that each set of the partition has a cardinality of at least a fixed number k. Among such kinds of partitions, which we call k-clusters, the objective is to find the k-cluster which minimises a certain cost derived from a given pairwise difference between objects which end up the same set. As a first step, this thesis introduces a general problem, denoted by (||.||,f)-k-cluster, which models the task to find a k-cluster of minimum cost given by an objective function computed with respect to specific choices for the cost functions f and ||.||. In particular this thesis considers three different choices for f and also three different choices for ||.|| which results in a total of nine different variants of the general problem. Especially with the idea to use the concept of parameterised approximation, we first investigate the role of the lower bound on the cluster cardinalities and find that k is not a suitable parameter, due to remaining NP-hardness even for the restriction to the constant 3. The reductions presented to show this hardness yield the even stronger result which states that polynomial time approximations with some constant performance ratio for any of the nine variants of (||.||,f)-k-cluster require a restriction to instances for which the pairwise distance on the objects satisfies the triangle inequality. For this restriction to what we informally refer to as metric instances, constant-factor approximation algorithms for eight of the nine variants of (||.||,f)-k-cluster are presented. While two of these algorithms yield the provably best approximation ratio (assuming P!=NP), others can only guarantee a performance which depends on the lower bound k. With the positive effect of the triangle inequality and applications to facility location in mind, we discuss the further restriction to the setting where the given objects are points in the Euclidean metric space. Considering the effect of computational hardness caused by high dimensionality of the input for other related problems (curse of dimensionality) we check if this is also the source of intractability for (||.||,f)-k-cluster. Remaining NP-hardness for restriction to small constant dimensionality however disproves this theory. We then use parameterisation to develop approximation algorithms for (||.||,f)-k-cluster without restriction to metric instances. In particular, we discuss structural parameters which reflect how much the given input differs from a metric. This idea results in parameterised approximation algorithms with parameters such as the number of conflicts (our name for pairs of objects for which the triangle inequality is violated) or the number of conflict vertices (objects involved in a conflict). The performance ratios of these parameterised approximations are in most cases identical to those of the approximations for metric instances. This shows that for most variants of (||.||,f)-k-cluster efficient and reasonable solutions are also possible for non-metric instances.
  • Die Arbeit beschäftigt sich mit dem abstrakten Clustering-Problem, für eine gegebene Menge von Objekten eine nach gewissen Qualitätsmaßen gemessene beste Partition zu bestimmen, sodass jede Teilmenge dieser eine gegebene feste Mindestkardinalität k besitzt. Als Qualitätsmaß werden insgesamt neun verschiedene konkrete Maßfunktionen diskutiert, die alle mit einer gegebenen paarweisen Distanz d auf den Objekten arbeiten. Für die neun Probleme, die sich daraus ergeben, werden Lösungsverfahren diskutiert, die hauptsächlich Methoden aus der parametrisierten und approximativen Algorithmik nutzen. Konkret wird zunächst die Komplexität dieser Probleme in Bezug auf die Mindestkardinalität k als Parameter diskutiert. Es wird gezeigt, dass alle neun Problemvarianten bereits für die Einschränkung auf k=3 NP-schwer sind, was nicht nur exakte polynomielle Lösbarkeit sondern auch effiziente parametrisierte Algorithmen für diese Parameterwahl sehr unrealistisch macht. Die Reduktionen, die für diese Komplexitätsschranken erstellt werden, zeigen außerdem, dass Approximierbarkeit nur dann möglich ist, wenn die gegebene Distanzfunktion d die Dreiecksungleichung erfüllt. Mit Einschränkung auf Dreiecksungleichung werden für acht der neun Problemvarianten polynomielle Approximationsalgorithmen mit beweisbarer Güte vorgestellt. Zwei dieser Algorithmen garantieren eine bestmögliche Approximationsgüte (unter der Annahme P!=NP), für die restlichen sechs lässt sich dagegen nur eine Güte beweisen, die von k abhängt. Des weiteren wird diskutiert, ob eine Einschränkung auf Instanzen im Euklidischen Raum zu leichterer Lösbarkeit führen kann. Insbesondere im Hinblick auf den sog. curse of dimensionality, wird untersucht, ob sich Vektoren in niedrig dimensionalen Räumen effizient partitionieren lassen. Es stellt sich heraus, dass NP-Schwere für die meisten der neun Problemvarianten auch für Punkte im zwei- oder drei-dimensionalen Raum bestehen bleibt, sogar in Kombination mit einer Einschränkung auf konstante Werte für k. Um Probleminstanzen zu betrachten, für die d die Dreiecksungleichung verletzt, muss, auch für approximative Lösungen mit beweisbarer Güte, mehr als polynomielle Laufzeit investiert werden. Mit einer Parametrisierung nach der Anzahl von Konflikten (Objektpaare, die die Dreiecksungleichung verletzen), lassen sich die zuvor für eingeschränkte Instanzen entwickelten polynomiellen Verfahren verallgemeinern. Konkret liefert dies Algorithmen, die beweisbare Approximationsgüten besitzen und deren Laufzeit polynomiell in der Eingabegröße und lediglich exponentiell in der Anzahl von Konflikten ist, sog. fixed parameter tractability für die Konfliktanzahl als Parameter. Als weitere Möglichkeit mit Verletzung der Dreiecksungleichung umzugehen, wird eine Relaxierung dieser um einen festen Faktor Alpha diskutiert. Auch für diese Sichtweise lassen sich die zuvor entwickelten Verfahren verallgemeinern. Dies führt zu rein polynomiellen Approximationsalgorithmen, deren Güte sich proportional zu Alpha verschlechtert.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Katrin Casel
URN:urn:nbn:de:hbz:385-11342
Advisor:Henning Fernau
Document Type:Doctoral Thesis
Language:English
Date of completion:2018/05/15
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2018/03/21
Release Date:2018/05/15
Tag:Parametrisierte Approximation
clustering; complexity; parameterised approximation
GND Keyword:Cluster; Komplexität; Modellierung; NP-hartes Problem; Näherungsverfahren
Comment:
DOI: https://doi.org/10.25353/UBTR-4241-5299-33XX
Institutes:Fachbereich 4 / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik

$Rev: 13581 $