On the approximation complexity hierarchy

DOI10.1007/978-3-642-18318-8_4zbMATH Open1314.68137OpenAlexW1606468290MaRDI QIDQ3075447FDOQ3075447

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• Title not available (Why is that?)
• On the complexity of approximating the Hadwiger number
• The relative complexity of approximate counting problems
• Complexity Approximation Principle
• On Parameterized Approximability
• A refinement of Cauchy-Schwarz complexity
• The complexity of approximating bounded-degree Boolean \(\#\)CSP

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)