Approximation of NP-Hard Problems: Algorithms and Complexity

NP 难问题的近似：算法和复杂性

• 批准号: 0098180
• 负责人: Sanjeev Arora
• 金额: $ 25.7万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098180&HistoricalAwards=false
• 关键词: Approximation; NP; Hard; Problems; Algorithms

Approximation of NP-hard problems: Algorithms and ComplexitySanjeev AroraPrinceton UniversityThe broad goal of the project is a study of the approximation properties ofNP-hard problems. NP-hard problems are those that do not have any efficientalgorithms if the classes P and NP are different, as is widely-believed. They arise in a varietyof application areas in science and technology, including scheduling, VLSIdesign, artificial intelligence, design of optimum networks, etc. Since we do not expect to solve these problems optimally, there is a need to design efficient approximation algorithms for them: algorithms that compute a solution whose cost is within a small factor of the optimum. The PI has beeninvolved in designing approximation algorithms during the past decade. He hasalso been part of an ongoing research program that shows that for many of these problems,computing approximate solutions is no easier than computing optimumsolutions. (In other words, approximation is also NP-hard.) Theseinapproximability results shed important light on the problems as well.The project takes a two-pronged approach, combining a search for goodapproximation algorithms with a search ---using the theory of probabilistically checkable proofs (PCPs)--- for inapproximability results. The project focusseson a collection of important algorithmic problems, including: learning mixturesof distributions (a problem important in AI and data mining/analysis),learning bayes nets and markov random fields (useful in speech recognition,machine vision, medical diagnoses systems etc.), lattice problems (useful incryptography and cryptanalysis), and graph coloring (a central problem in complexity theory).Progress, especially algorithmic progress, on any of these problems hasimportant consequences.

NP 困难问题的近似：算法和复杂性Sanjeev Arora 普林斯顿大学该项目的总体目标是研究 NP 困难问题的近似性质。正如人们普遍认为的那样，如果 P 类和 NP 类不同，则 NP 难问题是那些没有任何有效算法的问题。它们出现在科学技术的各个应用领域，包括调度、VLSI设计、人工智能、最优网络设计等。由于我们并不期望最优地解决这些问题，因此需要为它们设计有效的近似算法：计算成本与最优值相差很小的解决方案的算法。在过去的十年里，PI 一直参与设计近似算法。他还参与了一项正在进行的研究项目，该项目表明，对于许多此类问题，计算近似解并不比计算最佳解更容易。 （换句话说，近似也是 NP 难的。）这些不可近似性的结果也对问题提供了重要的启示。该项目采取了双管齐下的方法，将寻找好的近似算法与搜索结合起来——使用概率理论可检查证明（PCP）——用于不可近似的结果。该项目重点关注一系列重要的算法问题，包括：学习分布的混合（人工智能和数据挖掘/分析中的一个重要问题）、学习贝叶斯网络和马尔可夫随机场（在语音识别、机器视觉、医疗诊断系统等中有用） 、格问题（在密码学和密码分析中有用）和图着色（复杂性理论中的核心问题）。任何这些问题的进步，尤其是算法的进步，都会产生重要的后果。