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-hard问题的近似：算法和复杂性sanjeev arorprinceton大学该项目的主要目标是研究NP-hard问题的近似性质。NP困难的问题是那些没有任何有效的算法，如果类P和NP是不同的，正如人们普遍认为的那样。它们出现在各种科技应用领域，包括调度、vlsiddesign、人工智能、最优网络设计等。由于我们不期望最优地解决这些问题，因此需要为它们设计有效的近似算法：算法计算的解决方案的成本在最优的一个小因子内。在过去的十年里，PI一直参与设计近似算法。他还参与了一个正在进行的研究项目，该项目表明，对于许多这样的问题，计算近似解并不比计算最佳解容易。（换句话说，近似也是np困难的。）这些不近似的结果也为问题提供了重要的启示。该项目采用双管齐下的方法，将搜索良好的近似算法与使用概率可检验证明（pcp）理论搜索不可近似结果相结合。该项目侧重于一系列重要的算法问题，包括：学习混合分布（在人工智能和数据挖掘/分析中重要的问题），学习贝叶斯网络和马尔科夫随机场（在语音识别，机器视觉，医疗诊断系统等中有用），格问题（在密码学和密码分析中有用），以及图着色（复杂性理论中的中心问题）。任何这些问题的进展，尤其是算法的进展，都会产生重要的后果。