Parameterized Approximation Results for Clustering and Graph Packing Problems
Loading...
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2024-01-25
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2023
Major/Subject
Mcode
Degree programme
Language
en
Pages
106 + app. 124
Series
Aalto University publication series DOCTORAL THESES, 227/2023
Abstract
The domains of clustering and graph packing have been the focus of extensive research across multiple disciplines, including optimization, machine learning, data mining, computational geometry, and operations research. Many central problems in these domains are known to be NP-hard, prompting the exploration of approximation algorithms and parameterized algorithms as possible approaches, among others. In recent times, the paradigm of parameterized approximation algorithms, which strike a balance between approximation and polynomial-time computability on instances with small parameters, has gained renewed attention. This thesis comprises two distinct parts. In Part I, we design parameterized approximation algorithms for several clustering problems, significantly advancing the state of the art. In the center based k-clustering problem, which includes the classical problems of k-median, k-means, and k-center, we are given a point set P and the goal is to find a k-partition (clusters) of P along with a representative (center) for each partition to minimize certain clustering objective that is a function of the distance vector - the vector of distances between the centers and the points in the corresponding clusters. In the Norm k-Clustering problem, the clustering objective is a monotone norm of the distance vector. This objective is quite general and captures essentially all the clustering objectives studied so far. In this thesis, we design a novel and simple Efficient Parameterized Approximation Schemes (EPAS) framework for Norm k-Clustering in several metric spaces. This result unifies several existing EPASes that are known to be conceptually different. Moreover, our framework resolves many of the open problems related to advanced objectives, including modern constraints on fairness, robustness, and diversity. A notable contribution of this work is a new combinatorial measure of a metric space, which we call Scatter Dimension, that enables designing EPAS that is oblivious to the underlying metric space. Additionally, we address other clustering problems, namely Robust (k-z)-Clustering and Diversity-aware k-Median, and design tight parameterized approximation algorithms for them. Part II adopts a complementary approach, focusing on lower bounds for graph packing problems. In particular, we consider a notoriously hard problem called Set Packing and establish a parameterized dichotomy for the problem. A novel conceptual contribution to this dichotomy is the notion of compact instances, which remain challenging to solve despite their small size. Furthermore, we explore the connection between the approximating maximum independent set problem in k-claw-free graphs and several convex relaxations.Description
Supervising professor
Chalermsook, Parinya, Prof., Aalto University, Department of Computer Science, FinlandThesis advisor
Brzuska, Chris, Prof., Aalto University, Department of Computer Science, FinlandKeywords
clustering, graph packing, parameterized complexity, approximation algorithms
Other note
Parts
-
[Publication 1]: Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoardi, Dániel Marx, Roohani Sharma, Joachim Spoerhase. Parameterized Approximation Schemes for Clustering with General Norm Objectives. Accepted for publication in 64th IEEE Symposium on Foundations of Computer Science (FOCS), November 2023.
DOI: 10.1109/FOCS57990.2023.00085 View at publisher
- [Publication 2]: Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoardi, Dániel Marx, Roohani Sharma, Joachim Spoerhase. Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces. Submitted, August 2023
-
[Publication 3]: Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, Michał Osadnik. Clustering with Fair-Center Representation: Parameterized Approximation Algorithms and Heuristics. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Pages 1749–1759, August 2022.
DOI: 10.1145/3534678.3539487 View at publisher
-
[Publication 4]: Ameet Gadekar. On the Parameterized Complexity of Compact Set Packing. In Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM), Springer Nature Switzerland, Pages 359–370, March 2023.
DOI: 10.1007/978-3-031-27051-2_30 View at publisher
-
[Publication 5]: Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoardi, Joachim Spoerhase. Independent set in k-Claw-Free Graphs: Conditional χ-boundedness and the Power of LP/SDP Relaxations. Accepted for publication in The Workshop on Approximation and Online Algorithms (WAOA), September 2023. DOI:
DOI: 10.1007/978-3-031-49815-2_15 View at publisher
