Randomized Approximations of Parameterized Counting Problems

DOI10.1007/11847250_5MaRDI QIDQ3499723zbMATH OpenOpenAlexFDO

Authors Moritz Müller

Publication date 3 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11847250_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• On the parameterized complexity of approximate counting
• On parameterized counting
• scientific article; zbMATH DE number 1979521
• Parameterized random complexity
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS

Cited in

(19)

• Parameterized random complexity
• A fixed-parameter perspective on \#BIS
• scientific article; zbMATH DE number 1566488 (Why is no real title available?)
• scientific article; zbMATH DE number 1670534 (Why is no real title available?)
• A basic parameterized complexity primer
• Parameterized Derandomization
• On parameterized counting
• Monte-Carlo approximation algorithms for enumeration problems
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• Randomised enumeration of small witnesses using a decision oracle
• Confronting intractability via parameters
• Approximate counting and NP search problems
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• A fixed-parameter perspective on \#BIS
• Parameterized analogues of probabilistic computation
• On the parameterized complexity of approximate counting
• Approximate Counting with Deterministic Guarantees for Affinity Computation
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
• The parameterized complexity of probability amplification

This page was built for publication: Randomized Approximations of Parameterized Counting Problems

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