Approximation of NP-Hard Problems: Algorithms and Complexity

Princeton University, Princeton NJ

Investigators

Abstract

Approximation of NP-hard problems: Algorithms and Complexity Sanjeev Arora Princeton University The broad goal of the project is a study of the approximation properties of NP-hard problems. NP-hard problems are those that do not have any efficient algorithms if the classes P and NP are different, as is widely-believed. They arise in a variety of application areas in science and technology, including scheduling, VLSI design, 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 been involved in designing approximation algorithms during the past decade. He has also been part of an ongoing research program that shows that for many of these problems, computing approximate solutions is no easier than computing optimum solutions. (In other words, approximation is also NP-hard.) These inapproximability results shed important light on the problems as well. The project takes a two-pronged approach, combining a search for good approximation algorithms with a search ---using the theory of probabilistically checkable proofs (PCPs)--- for inapproximability results. The project focusses on a collection of important algorithmic problems, including: learning mixtures of 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 in cryptography and cryptanalysis), and graph coloring (a central problem in complexity theory). Progress, especially algorithmic progress, on any of these problems has important consequences.