Approximation of NP-Hard Problems: Algorithms and Complexity

点击翻译按钮获取中文摘要

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.