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

AF：小：约束满足近似性的一些前沿及相关问题

• 批准号: 1115525
• 负责人: Venkatesan Guruswami
• 金额: $ 38万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115525&HistoricalAwards=false
• 关键词: AF; Small; Some; Frontiers; Approximability

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.

许多重要的计算任务可以被转换为优化问题，其目标是找到一个遵守规定约束的解决方案，最大化或最小化某个目标值。不幸的是，这些问题中的大多数是NP-难的最佳解决方案。 科普这一难题的最广泛研究和最成功的方法之一是解决近似算法，这是一种有效的算法，可以找到具有可证明质量保证的解决方案。这种方法很吸引人，因为它不对问题实例做任何假设。此外，在典型的情况下，该算法可以执行得比证明的界限。在这个问题上的研究已经取得了巨大的进步，对于许多问题，我们现在有很好的近似算法以及强大的互补硬度结果。事实上，对于大类问题，一个共同的边界称为“唯一游戏难度”已被确定为已知技术可实现的最佳近似。尽管所有这些进展，某些类别的优化问题已经回避了现有的技术，它们的地位仍然是开放的。此外，最近的突破开辟了令人兴奋的研究课题，这是以前无法想象的。拟议的研究将确定和调查几个这样的前沿领域，其中缺乏进展，无论是在基本技术方面，以及最终结果的声明。研究的主题将包括强半定规划松弛的算法能力，以解决一些困难的优化问题，约束满足风格的问题，其中一个解决方案服从一个全球性的财产寻求，和（近）可满足的约束满足问题的情况下的近似性。此外，还将对一些探索性课题进行初步研究，如与参数化复杂性的联系，以及在某些已知结果中绕过唯一博弈猜想的可能性等。拟议的研究将揭示抽象了实践中出现的一些核心计算任务的基本优化问题的可近似性。研究和外联活动的目的是促进近似和约束满足社区之间的思想交流，这两个社区在很大程度上是通过不同的方法取得进展的，互动很少。 在教育方面，该项目将培训和指导研究生，并为他们提供一个激励性的研究环境。研究结果，适当的，将被整合到一个统一的课程，突出了近似算法和不可近似结果的新兴融合。