Deterministic algorithm improves approximation of matrix permanents
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Data Structures and AlgorithmsComputational Complexity
Summary
Calculating the permanent of a matrix—a number that counts certain ways to match items—is very hard, especially for large matrices with many numbers. The authors developed the first step-by-step method that runs efficiently and gives a closer approximation than before, improving from exponential to subexponential error. They use techniques from optimization and graph theory, looking at the matrix as a network and carefully estimating connections to reduce errors. This makes it easier, in theory, to estimate permanents without random guesses.
permanentmatrixapproximation algorithmdeterministic polynomial timeconvex optimizationbipartite graphmatchingcorrelation decaycombinatorics
Authors
Sergei Kudria, Jason Luo, Mahbod Majid
Abstract
We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.