Geodesic
Approximating permanents and hafnians
Discrete analysis (2017) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

We prove that the logarithm of the permanent of an nxn real matrix A and the logarithm of the hafnian of a 2nx2n real symmetric matrix A can be approximated within an additive error 1 > epsilon > 0 by a polynomial p in the entries of A of degree O(ln n - ln epsilon) provided the entries a_ij of A satisfy delta a_ij 1 for an arbitrarily small delta > 0, fixed in advance. Moreover, the polynomial p can be computed in n^{O(ln n - ln epsilon)} time. We also improve bounds for approximating ln per A, ln haf A and logarithms of multi-dimensional permanents for complex matrices and tensors A.
Publié le : 
@article{DAS_2017_a18,
     author = {Alexander Barvinok},
     title = {Approximating permanents and hafnians},
     journal = {Discrete analysis},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2017_a18/}
}
TY  - JOUR
AU  - Alexander Barvinok
TI  - Approximating permanents and hafnians
JO  - Discrete analysis
PY  - 2017
UR  - http://geodesic.mathdoc.fr/item/DAS_2017_a18/
LA  - en
ID  - DAS_2017_a18
ER  - 
%0 Journal Article
%A Alexander Barvinok
%T Approximating permanents and hafnians
%J Discrete analysis
%D 2017
%U http://geodesic.mathdoc.fr/item/DAS_2017_a18/
%G en
%F DAS_2017_a18
Alexander Barvinok. Approximating permanents and hafnians. Discrete analysis (2017). http://geodesic.mathdoc.fr/item/DAS_2017_a18/