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 Arora普林斯顿大学该项目的主要目标是研究NP-hard问题的近似性质。NP难问题是那些没有任何有效的算法，如果类P和NP是不同的，因为是广泛认为。他们出现在各种各样的应用领域的科学和技术，包括调度，VLSIdesign，人工智能，设计的最佳网络等，因为我们不希望以最佳的方式解决这些问题，有必要为他们设计有效的近似算法：算法计算的解决方案，其成本是在一个小的因素的最佳。在过去的十年中，PI一直参与设计近似算法。他还参与了一项正在进行的研究计划，该计划表明，对于许多此类问题，计算近似解并不比计算最优解容易。(In换句话说，近似也是NP难的。）这些不可近似性的结果揭示了重要的问题，以及。该项目采取了双管齐下的方法，结合搜索良好的近似算法搜索--使用概率可检查证明（PCP）的理论--为不可近似性的结果。该项目专注于一系列重要的算法问题，包括：学习混合分布（AI和数据挖掘/分析中的重要问题），学习贝叶斯网络和马尔可夫随机场（用于语音识别，机器视觉，医疗诊断系统等），格问题（有用的密码学和密码分析）和图着色（复杂性理论中的一个中心问题）。