Public defence in Computer Science, M.Sc. Ameet Gadekar
When
Where
Event language(s)
Title of the doctoral thesis: Parameterized Approximation Results for Clustering and Graph Packing Problems
Doctoral student: Ameet Gadekar
Opponent: Dr. Chien-Chung Huang, École Normale Supérieure, France
Custos: Associate Professor Parinya Chalermsook, Aalto University School of Science, Department of Computer Science
The thesis explores the intricate domains of clustering and graph packing, spanning optimization, machine learning, data mining, computational geometry, and operations research. Addressing NP-hard problems, it adopts the dual lenses of approximation algorithms and parameterized algorithms, with an emphasis on the emerging paradigm of parameterized approximation algorithms.
The thesis unfolds in two distinct parts. In Part I, the focus is on designing parameterized approximation algorithms, pushing the boundaries of existing knowledge. Introducing a novel concept of Scatter Dimension, the thesis presents an Efficient Parameterized Approximation Schemes (EPAS) framework for several clustering problems, encompassing classical problems like k-median, k-means, and k-center, across several metric spaces, unifying previously disparate results, and providing new results for advanced objectives that incorporate fairness and robustness. The thesis also tackles other clustering problems, including Robust clustering and Diversity-aware clustering, presenting tight parameterized approximation algorithms.
Part II complements the first part, focusing on lower bounds for graph packing problems. The thesis presents a parameterized dichotomy for the notoriously hard Set Packing problem. It also explores the intricate connection between approximating the maximum independent set problem in k-claw-free graphs and various convex relaxations.
Thesis available for public display 10 days prior to the defence at: https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/
Contact details:
| ameet.gadekar@aalto.fi |
Doctoral theses in the School of Science: https://aaltodoc.aalto.fi/handle/123456789/52