×

The quest for strong inapproximability results with perfect completeness. (English) Zbl 07475107


MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
68R07 Computational aspects of satisfiability
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI Link