1
$\begingroup$

My question concerns approximating permanent of an $n$-by-$n$ matrix.

Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and accuracy $\epsilon$ (e.g., in the following paper by Linial et al.: "A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents.")

In order to get an FPTAS, we have to choose $\epsilon$ as a function of $n$. For examples it is mentioned in Linial's paper that for the purpose of approximating the permanent, it suffices to choose $\epsilon=n^{-2}$ (last paragraphs of Section 1 of the above paper).

Anyone could give me some hints why this choice of $\epsilon$ is sufficient?

Improve this question
$\endgroup$
1
  • $\begingroup$ Because you can pad the input matrix with diagonal entries to dimension, say, $m=n/\epsilon$ while preserving the permanent, and then $m^{-2}<\epsilon$. $\endgroup$
    – Emil Jeřábek
    Commented Apr 20, 2015 at 9:40

0

Reset to default

You must log in to answer this question.