Grant: Discovery Grants Program - Individual

The proposed Discovery Grant (DG) research program will investigate combinatorial optimization problems with the long-term goal of advancing our understanding of the problems from two viewpoints: 1) The approximability of central problems in the field in the worst-case regime of analysis of algorithms, and 2) The complexity of such problems in the beyond-worst case regime, including, but not restricted to, through the lens of parameterized complexity. To realize these long-term goals, this program proposes the following short-term objectives: (i) Generalized Approximation Frameworks. The development of approximation algorithms typically is a slow process, especially for prominent problems for which improvements in approximation factor usually have far-reaching impact. Any such improvement typically happens after meticulous analysis of the problem to uncover new structural properties not previously known to the research community. This leads to hyper-customized and complicated approximation algorithms. Thus, this objective emphasizes frameworks that require a minimal knowledge about the structure of the input instance. Such frameworks will allow us to design approximation algorithms that are applicable to a large spectrum of questions. (ii) Optimization in Applied Settings. In spite of all their rigour and beauty, many classical problems defined in the early days of combinatorial optimization fail to capture the requirements of modern-day applications. To meet such needs, we either have to part ways with the tradition of worst-case analysis of the algorithms and consider the special instances of the problem that are relevant to our applications, or devise more sophisticated algorithms that can rise to the challenge posed by the new generations of combinatorial optimization problems. The goal of this objective is to investigate these two potential solutions by building on the past success of my research. (iii) Hardness Techniques for Approximation. While the design of approximation algorithms (upper bounds) has been an active field of research in the past few decades, the dual area of hardness of approximation has been relatively dormant. Many breakthroughs have taken place in improving the best known algorithm (in terms of approximation factor, running time, parameterized complexity, etc.). For this objective, we join a recent movement that seeks possible breakthroughs for hardness results as well. While fascinating new techniques have been introduced in the past few years, this field of study is still young, and ripe with opportunities for impactful research. This research is anticipated to develop tools that generate a refined chart of computability and approximability of combinatorial optimization problems and move a few lower and upper bounds for such problems along the way. Additionally, I foresee a significant influence outside of my field and in the area of practical, fast algorithms.