On the approximation complexity hierarchy

DOI10.1007/978-3-642-18318-8_4MaRDI QIDQ3075447zbMATH OpenOpenAlexFDO

Authors Magnus Bordewich

Publication date 15 February 2011

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-18318-8_4

Mathematics Subject Classification ID

Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The relative complexity of approximate counting problems
• scientific article; zbMATH DE number 1670534
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• A fixed-parameter perspective on \#BIS

Cited in

(7)

• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• scientific article; zbMATH DE number 1206797 (Why is no real title available?)
• On the complexity of approximating the Hadwiger number
• The relative complexity of approximate counting problems
• Complexity Approximation Principle
• A refinement of Cauchy-Schwarz complexity
• On Parameterized Approximability

This page was built for publication: On the approximation complexity hierarchy

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