Research Projects

Combinatorial optimization is an area in theoretical computer science wherein we want to find an optimal (minimum/maximum) object from a discrete set of objects. Most interesting discrete problems are NP-hard, i.e., the existence of polynomial-time algorithms that find optimal solutions for such problems is extremely unlikely. The traditional approach is to settle for polynomial-time approximation algorithms with a provable guarantee on the quality of the solutions found. Amongst the myriad problems studied in this field, in this project we focus our attention to two broad categories of problems: Clustering and Covering (C&C). These categories encompass a wide range of problems stemming from diverse areas such as unsupervised learning, operations research, algorithmic graph theory, computational economics and social choice, and sensor networks, just to mention a few. Such practical applications often come with inherent constraints, such as fairness – wherein we may want a proportional representation of different demographics of the population being clustered into, say, electoral constituencies; or capacities – wherein a school/hospital/cellphone tower has practical limitations on the number of clients that can be served simultaneously. If an algorithm is oblivious to these aspects, it may produce infeasible solutions. Hence, such constraints need to be made a part of the formal model itself. Polynomial-time approximation algorithms occasionally fall short of obtaining “good” solutions in presence of additional constraints – either the algorithms tend to be quite complex, or the approximation ratios achieved are impractical. On the other hand, recent research in parameterized—or Fixed-Parameter Tractable (FPT)—approximation algorithms has unequivocally shown that, by slightly relaxing the requirement of polynomial running time, one can greatly simplify the algorithmic ideas at the expense of moderate enumeration of the search space. In this project, we propose to use the ever-growing toolbox of FPT approximation for designing state-of-the-art algorithms for constrained C&C problems. In this context, our goal is to find the most relevant constraints among fairness, capacities, fault-tolerance, structural restrictions on the solution, and so on. Recently, the PI has contributed towards the design of a black-box reduction for handling the outliers in the data, by presenting a parameterized reduction from outlier to outlier-free clustering problems. Such algorithms provide a conceptual separation between the basic combinatorial problem, and the additional constraint. In this project, the ideal outcome would be to find such parameterized reductions from constrained to the unconstrained versions, thereby obviating the need to reinvent the wheel. To deal with the minutiae of each constraint, we will likely have to work with novel parameterizations, which will undoubtedly find applications in further research and practice.