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"”.
-
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 …
-
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 …
-
Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης
… this normalizing factor can be approximated with FPRAS, (i.e. with an arbitrarily small multiplicative error in polynomial time). It remains an open question whether this normalizing factor can be computed either exactly or with a small absolute error. However we show that the latter is impossible …
-
Counting below #P: Classes, problems and Descriptive Complexity
… κάποια υποκλάση των προβλημάτων που επιδέχονται FPRAS αντίστοιχα. Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό …
-
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 …
-
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 …
-
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 …
-
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.
-
Optimization and Parallelization of RegEx Based Information Extraction
… randomized approximation schemes (FPRAS).