Many modern tasks, from organizing datasets to identifying similar points or comparing DNA sequences, reduce to fundamental computational problems. As datasets grow, a common strategy is to relax seeking optimal solutions and instead use approximation algorithms to gain speed. By studying the hardness of approximation, my work establishes fundamental limits of this speed-accuracy trade-off, clarifying when we cannot significantly improve known algorithms, even with approximate solutions.
In this talk, I will present my contributions through two research programs.
First, I consider problems solvable in polynomial time, such as computing the closest pair in large datasets and finding a fixed-size set cover, a task that arises in computational proteomics. Using the lens of fine-grained and parameterized complexity, I show that for these problems no approximation algorithm yields a significant asymptotic speedup over exact methods.
Second, I turn to NP-hard geometric optimization problems, including clustering and Steiner tree, central to machine learning, logistics, and network design. For these problems, approximation is unavoidable, and I prove strong inapproximability results that identify the ultimate limits of approximation.
Zoom link: https://icts-res-in.zoom.us/j/99300784911?pwd=EYAYGNLydB4HKuUtCfpUnLvjmGYZjv.1
Meeting ID: 993 0078 4911
Passcode: 203040