Approximation of NP-Hard Problems: Algorithms and Complexity

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

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.