Dokument: FPT-Approximation for k-Min-Sum-Radii and Practical Advances for k-Means

Titel:	FPT-Approximation for k-Min-Sum-Radii and Practical Advances for k-Means
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=72444
URN (NBN):	urn:nbn:de:hbz:061-20260305-110011-7
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Drexler, Lukas [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 7,62 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 03.03.2026 / geändert 03.03.2026
Beitragende:	Prof. Dr. Schmidt, Melanie [Gutachter] Röglin, Heiko [Gutachter]
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibung:	In a world of ever-growing amounts of data, the automatic discovery of meaningful structure has become increasingly important. Clustering addresses this challenge by grouping data points into subsets based on their similarity, without the need for labeled data. It can therefore be viewed as a form of unsupervised machine learning. Another way of looking at it is through the lens of combinatorial optimization and algorithmics. One way of formulating clustering as an optimization problem is the following: given a point set $P$ and a distance function $d$ on this set, find a set of at most $k$ centers and an assignment of points to those centers, so as to minimize some objective function. In some applications, solutions are additionally required to satisfy further constraints. For instance, a center may only serve a certain number of points, or the points may belong to different protected groups, with the requirement that no group is underrepresented in any cluster. In this thesis, we mainly study two objectives: $k$-Means and $k$-Min-Sum-Radii. It is structured into three parts. Part I provides an introduction and establishes the formal definitions, concepts, and notation used throughout the thesis. Part II is devoted to $k$-Min-Sum-Radii clustering and the more theoretical aspects of clustering. This objective is of special interest, as it can exhibit counterintuitive behavior and differs significantly from other, seemingly related objectives. As a result, many standard algorithmic techniques that are successful for objectives such as $k$-Center or $k$-Median fail to apply. After investigating several structural properties of $k$-Min-Sum-Radii, we present two FPT approximation algorithms for different variants. The first is a $(1+\epsilon)$-approximation for Euclidean $k$-Min-Sum-Radii. The second is a $(6+\epsilon)$-approximation for $k$-Min-Sum-Radii in general metrics, and with mergeable constraints, a class of constraints that share properties. Part III focuses on the $k$-Means objective from a more practical perspective. We introduce a new algorithm, which is extensively tested against other commonly used algorithms. While it can be shown to yield a constant-factor approximation, its main strength lies in its practical performance. Across most of the experiments, it outperforms the other algorithms in terms of cost, while remaining competitive in terms of runtime. Furthermore, we explore the algorithm's ability to approach the globally optimum solution on a selection of datasets for which the optima are known. Although the algorithm typically comes very close to optimality, it consistently fails to achieve the final step. This observation motivates a brief discussion of emerging questions concerning dataset clusterability and the ability of this class of algorithms to reach globally optimal solutions.
Lizenz:	Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung 4.0 International Lizenz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik
Dokument erstellt am:	05.03.2026
Dateien geändert am:	05.03.2026
Promotionsantrag am:	14.01.2026
Datum der Promotion:	26.02.2026