Parameterized Approximation Results for Clustering and Graph Packing Problems

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.