AF: Small: Challenges in Hardness of Approximation

点击翻译按钮获取中文摘要

A major focus in theoretical computer science is to determine the ``work" required to solve specific computational problems, efficiency being the usual goal. The work needed to solve a problem, or ``running time'', is often expressed in terms of a number n related to the problem size. A problem is ``easy'' if it is solvable by a ``fast'' algorithm (i.e. whose running time is a polynomial in n). Fast algorithms lie at the heart of much everyday computation, such as Web search engines. In contrast, for certain problems the running time is, unavoidably, an exponential function of n; hence even medium-size instances are unsolvable in practice. For other problems, including those in the class called ``NP", the exact relationship between running time and size remains unknown. Understanding and mapping the boundary between feasible and infeasible problems is the domain of computational complexity.Problems in the class ``P'' can be solved in polynomial time; problems in ``NP'', for which a candidate solution can be checked in polynomial time, cannot be solved in polynomial time today and are therefore infeasible. One way to mitigate this infeasibility is to obtain a good but approximate solution. Since the quality of an approximation may vary widely, an obvious question is how well a computationally feasible algorithm can approximate the exact solution. A significant issue is knowing whether the algorithm achieves the best possible performance; if not, a better algorithm should be sought.PI's proposed research involves determining the best approximation ratio that is computationally feasible (which amounts to proving that any better ratio is not feasible). It turns out that these ratios can be classified precisely and this research has several connections to mathematics, especially Fourier analysis and geometry. The last two decades have seen a huge progress on these questions and the current proposal is aimed at identifying and working on several challenges that are still wide open. The research goals of the proposal will be integrated with teaching, mentoring and dissemination activities. The research will involve participation of graduate students and post-doctoral fellows. The PI plans to develop research courses at graduate level to introduce budding researchers to the area. The dissemination activities will involve writing expository articles and an introductory book and organizing workshops. The PI will welcome any opportunities to guide under-graduate (and high-school) students who might be interested in having research exposure.