Research Projects

Many combinatorial optimization problems are NP-hard, meaning that efficient algorithms are not expected to compute their optimal solutions. Approximation algorithms aim to find efficient algorithms that compute solutions of cost that is close to optimal. The study of algorithms involves determining the performance of an algorithm over all possible input instances, known as the "worst-case analysis." However, simple heuristics often outperform algorithms with rigorous worst-case guarantees on "practical instances." The "Beyond worst-case analysis" (BWCA) of algorithms aims to explain this phenomenon by defining rigorous models of practical instances and designing algorithms specifically for these families with significantly better theoretical guarantees than general instances. BWCA bridges the gap between theory and practice in the study of algorithms and is of interest to theoreticians as it helps understand which aspects of a problem make it computationally hard. The inherent structure in practical instances can be modelled as certain families of random/semi-random instances or families of instances satisfying other structural properties. New algorithmic techniques have been developed in the last decade, making progress on long-standing open questions. This project proposes studying fundamental questions in this area, such as designing approximation algorithms and approximate recovery algorithms based on these new techniques for natural random/semi-random families of instances and instances satisfying various structural properties.