Random path method with pivoting for computing permanents of matrices

DOI10.1016/J.AMC.2006.07.070zbMATH Open1135.65023OpenAlexW2123908066MaRDI QIDQ870138FDOQ870138

Fengshan Bai, Xiaoyan Liu, Lin-Song Shi, Heng Liang

Publication date: 12 March 2007

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2006.07.070

Recommendations

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• The method of random determinants for estimating the permanent
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• An analysis of Monte Carlo algorithm for estimating the permanent
• Computing sparse permanents faster

zbMATH Keywords

numerical examplesunbiased estimatorMonte Carlo methodpermanentrandom path methodRasmussen method

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40)

Cites Work

• Matching theory
• Approximating the number of monomer-dimer coverings of a lattice.
• Combinatorial matrix theory
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• Title not available (Why is that?)
• Title not available (Why is that?)
• Permanents
• Approximating the Permanent
• A Monte-Carlo Algorithm for Estimating the Permanent
• Title not available (Why is that?)
• Approximating the permanent: A simple approach
• Title not available (Why is that?)
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• An upper bound for the permanent of \((0,1)\)-matrices.
• An analysis of Monte Carlo algorithm for estimating the permanent
• Systems of distinct representatives. II
• Clifford algebras and approximating the permanent

Cited In (4)

• Path methods for strong shift equivalence of positive matrices
• A hybrid algorithm for multi-homogeneous Bézout number
• Title not available (Why is that?)
• Flexible manufacturing system selection using a combinatorial mathematics-based decision-making method

This page was built for publication: Random path method with pivoting for computing permanents of matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870138)