AF: Small: Some Frontiers in the Approximability of Constraint Satisfaction and Related Problems

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

Many important computational tasks can be cast as optimization problems, where the goal is to find a solution obeying stipulated constraints that maximizes or minimizes a certain objective value. Unfortunately, most of these problems are NP-hard to solve optimally. One of the most extensively studied and successful approaches to cope with this intractability is to settle for approximation algorithms, which are efficient heuristics that find solutions with provable guarantees on quality. This approach is appealing as it does not make any assumptions about the problem instance. Further, on typical instances the algorithm could perform much better than the proven bound. Research in this subject has made huge strides, and for many problems we now have good approximation algorithms as well as strong complementary hardness results. In fact, for large classes of problems, a common frontier called ``Unique-Games hardness'' has been identified as the best approximation achievable with known techniques.Despite all this progress, certain classes of optimization problems have eluded existing techniques and their status remains wide open. Also, the recent breakthroughs open up exciting research topics that could not be imagined before. The proposed research will identify and investigate several such frontiers where progress has been lacking, both in terms of the underlying techniques as well as the end result statements. The topics studied will include the algorithmic power of strong semidefinite programming relaxations to tackle some difficult optimization problems, constraint satisfaction style problems where a solution obeying a global property is sought, and the approximability of (near)-satisfiable instances of constraint satisfaction problems. Initial investigations into exploratory topics such as connections with parameterized complexity and the possibility of bypassing the Unique Games conjecture in some of its known consequences will also be pursued.The proposed research will shed light on the approximability of basic optimization problems that abstract some of the core computational tasks arising in practice. The research and outreach activities will aim to foster a cross-fertilization of ideas between the approximation and constraint satisfaction communities, which have largely progressed via disparate methods with little interaction. On the education front, the project will train and mentor graduate students and provide a stimulating research environment for them. The research findings, as appropriate, will be integrated into a unified course highlighting the emerging confluence of approximation algorithms and inapproximability results.