AF: Small: Hardness of Approximation Meets Parameterized Complexity

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

Many important optimization problems are not tractable. Two typical ways to cope with the intractability of optimization problems is to either design algorithms that find solutions whose cost is close to the optimum or design algorithms which find exact solutions but run in time purely polynomial in the input size but exponential (or possibly worse) in terms of a parameter of the problem (referred to as fixed parameter tractability runtime). For several optimization problems, it is possible to prove that (i) finding good approximate solutions is as hard as finding optimal solutions, and (ii) for specific parameters of interest, under plausible assumptions, the problem does not admit algorithms with fixed parameter tractability runtime. In fact, for many important problems, it is possible to prove that for specific parameters of interest, and under plausible assumptions, the problem does not even admit algorithms computing only an approximate solution while having fixed parameter tractability runtime. This project concerns the study of such inapproximability results. The research goals of the project will be integrated with teaching, mentoring, and dissemination activities. The research will involve participation of graduate students and post- doctoral fellows. This project deals with the challenging task of developing the nascent area arising from the intersection of hardness of approximation and parameterized complexity, drawing from toolkits in coding theory, extremal combinatorics, and analysis of Boolean functions. The problems that are planned to be investigated in this project are essentially the same problems pursued in the 1990s in the non-deterministic polynomial (NP) world which then formed the bedrock of hardness of approximation results therein. In the NP world, these results (and the techniques developed) served as the starting point to prove the inapproximability of various other problems of interest to the Theoretical Computer Science community (such as Clustering, Travelling Salesman Problem, Scheduling problems, etc.). Upon successfully answering the questions in this project, researchers in parameterized complexity will have sufficient results and tools at their disposal to prove the hardness of approximation for the problems of their interest. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.