This post continues my series on favorite theorems of the 21st century, in each year and each of the seven major subject categories. For an overview of the categories and my previous selections, see this earlier post. My choice for 2001 in Algorithms and Complexity is the algorithm of Jerrum, Sinclair and Vigoda (Jerrum et al. 2004) that can efficiently approximate the permanent of a matrix with non-negative entries to any given accuracy.
In this previous blog post about the Algorithms and Complexity category, we considered only decision problems, that is, problems with a “Yes” or “No” answer. For example, we discussed the -SAT problem, where the task is to decide whether there exists a truth assignment to the variables that satisfies all clauses. More generally, we may ask to count how many such assignments exist. As another example, there is a decision problem of determining whether there exists a perfect matching in a given graph , and the corresponding counting problem asks how many such matchings there are.
Note that the -SAT problem is in the class NP because any satisfying assignment serves as a “certificate” that the problem has a “Yes” answer, and the correctness of this certificate can be verified in polynomial time. The counting version asks us to count such certificates. Similarly, any perfect matching in a graph is a certificate that the graph has a perfect matching. More generally, for any problem in class NP, we may formulate a counting problem asking for the number of corresponding certificates. The class of all such counting problems is denoted . The class of counting problems solvable in polynomial time is called FP, and, similarly to PNP, there is a widely believed conjecture that FP. We say that a counting problem is -hard if any problem in reduces to it in polynomial time, and, similarly to NP-hardness for decision problems, -hardness is convincing evidence that a counting problem is intractable.
Amazingly, some -hard problems can be efficiently solved approximately to any given accuracy. A famous example is the problem of computing the permanent. Let be an matrix with integer entries . The permanent of is where the sum is over all permutations of . The evaluation of the permanent of a matrix is an old and well-studied problem going back to at least the 1812 memoirs of Binet and Cauchy. In 1979, Valiant (Valiant 1979) proved that exact computation of the permanent is -hard, even if all are either or . However, Jerrum, Sinclair and Vigoda (Jerrum et al. 2004) presented in 2001 an algorithm which, for any matrix with non-negative entries, computes (with high probability) an arbitrarily close approximation to its permanent in time that depends polynomially on the input size and the desired error. Given Valiant’s result, this is essentially the best we could hope for.
In general, a polynomial-time approximation scheme (PTAS) is an algorithm which, given a parameter and an instance of an optimization problem of length , produces in time a solution which differs from the optimal one by a factor of . Here, is a polynomial which depends on . If the running time is bounded by a polynomial in both and , we say that the problem has a fully polynomial-time approximation scheme (FPTAS). If the corresponding algorithm is randomized, we call it a fully polynomial randomized approximation scheme (FPRAS). More concretely, a FPRAS for the permanent computation is a randomized algorithm which, given an matrix and as an input, runs in time polynomial in and , and outputs a (random) number such that The probability here can be made arbitrarily close to by running the algorithm several times and averaging the outputs.
The proof of Theorem first treats the important special case when all entries are either or , and then extends to the general case of arbitrary non-negative entries. The starting point is the 1986 observation of Jerrum, Valiant and Vazirani (Jerrum et al. 1986) that the approximate permanent computation for - matrices is equivalent to sampling perfect matchings from a bipartite graph almost uniformly at random. The latter problem is solved using the “Markov chain Monte Carlo” method, first proposed by Broder (Broder 1986) in 1986, which considers a random walk on the space of all perfect and “near-perfect” matchings (that is, matchings with unmatched vertices) on , such that, no matter where we start the walk, its position after polynomially many steps is nearly uniformly random. The method works unless the number of perfect matchings is negligible compared to the number of near-perfect ones. Jerrum, Sinclair and Vigoda (Jerrum et al. 2004) developed a modified version of this algorithm, in which each near-perfect matching gets a weight in such a way that the number of weighted near-perfect matchings becomes not much higher than the number of perfect matchings.