Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 9 of 9 for “"FPRAS"”.

  1. FPRAS Approximation of the Matrix Permanent in Practice

    … Polynomial Randomized Approximation Scheme (FPRAS) for the matrix permanent which has previously only been described theo- retically and with big-Oh runtime analysis. We demonstrate that the constant factors hidden by the big-Oh analysis result in computational infeasibility. We explore the …

    rice Repository record for FPRAS Approximation of the Matrix Permanent in Practice (opens in a new tab)

  2. On Hashing-Based Approaches to Approximate DNF-Counting

    … polynomial randomized approximation scheme (FPRAS). For CNF constraints, hashing-based techniques are highly successful. It was recently shown that hashing techniques also yield an FPRAS for DNF counting. Our analysis, however, shows that the proposed hashing approach provides poor time …

    rice Repository record for On Hashing-Based Approaches to Approximate DNF-Counting (opens in a new tab)

  3. Counting below #P: Classes, problems and Descriptive Complexity

    … κάποια υποκλάση των προβλημάτων που επιδέχονται FPRAS αντίστοιχα. Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό …

    athens Repository record for Counting below #P: Classes, problems and Descriptive Complexity (opens in a new tab)

  4. On structural and descriptive complexity of hard counting problems the decision version of which is easy

    … class of approximable counting problems, namely FPRAS, and we define three counting problems, that each has a decision version in RP, which is not known to lie in P. We prove that one of them, namely #NonZerosForPIT, has an fpras.3) We examine the problem #Exact Matchings, which is one of the …

    greece Repository record for On structural and descriptive complexity of hard counting problems the decision version of which is easy (opens in a new tab)

  5. The complexity of counting problems

    … polynomial randomised approximation scheme (fpras) for the number of forests of a dense graph is created. This leads to the following generalisation:</p><p>Theorem: For any rational x ≥ 1, there exists a fully polynomial randomised approximation scheme for evaluating the Tutte polynomial of …

    oxford Repository record for The complexity of counting problems (opens in a new tab)

  6. Constrained Counting and Sampling: Bridging the Gap Between Theory and Practice

    … Polynomial Randomized Approximation Scheme (FPRAS) that does not involve Monte Carlo steps. We demonstrate the utility of the above techniques on various real applications including probabilistic inference, design verification and estimating the reliability of critical infrastructure networks …

    rice Repository record for Constrained Counting and Sampling: Bridging the Gap Between Theory and Practice (opens in a new tab)

  7. Vertex enumeration and counting for certain classes of polyhedra

    … procedures are of interest. In particular, some fpras for counting vertices of polyhedra associated with 0-1 Permanent, Down Sets, Independent Sets, 0-1 Knapsack Problems, 2 by n transportation problems, matroids and matchings in a non-bipartite graph are developed.

    whiterose Download PDF for Vertex enumeration and counting for certain classes of polyhedra (opens in a new tab)