Portal de Periódicos da CAPES

A Monte-Carlo Algorithm for Estimating the Permanent

1993; Society for Industrial and Applied Mathematics; Volume: 22; Issue: 2 Linguagem: Inglês

10.1137/0222021

1095-7111

Narendra Karmarkar, Richard M. Karp, Richard Lipton, László Lovász, Michael Luby,

Matrix Theory and Algorithms

Let A be an $n \times n$ matrix with 0-1 valued entries, and let ${\operatorname{per}}(A)$ be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a "good in the relative sense" estimate of ${\operatorname{per}}(A)$ and has running time ${\operatorname{poly}}(n)2^{{n / 2}} $, where ${\operatorname{poly}}(n)$ denotes a function that grows polynomially with n.