PreprintCC BY 4.0arXiv
A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix
Abstract
For every fixed 0<ε≤1, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix A∈ℝ≥0n× n, returns Q satisfying per A≤ Q≤(1+ε)nper A.
Related
- Subexponential Approximation of the Permanent in Deterministic Polynomial Time
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
- Beyond the Bethe Approximation of the Permanent
- Optimal girth-dependent bounds for the Bethe approximation of the permanent
- Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization
BibTeX
@misc{dong2026deterministic,
title = {{A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix}},
author = {Dingding Dong and Vishesh Jain},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11049},
eprint = {2609.11049},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11049},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A deterministic (1+ε)^n approximation for the permanent of a nonnegative matrix
AU - Dingding Dong
AU - Vishesh Jain
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11049
UR - https://arxiv.org/abs/2609.11049
AB - For every fixed 0<ε≤1, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix A∈ℝ_≥0^n× n, returns Q satisfying per A≤ Q≤(1+ε)^nper A.
ER -