Strong lower bounds on the approximability of some NPO PB-complete maximization problems

DOI10.1007/3-540-60246-1_129MaRDI QIDQ3569014zbMATH OpenOpenAlexFDO

Authors Viggo Kann

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60246-1_129

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polynomially bounded minimization problems which are hard to approximate
• scientific article; zbMATH DE number 751135
• The approximability of constraint satisfaction problems
• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 1559517

Cited in

(11)

• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems
• Dominating sets and connected dominating sets in dynamic graphs
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• Time-approximation trade-offs for inapproximable problems
• Structure in approximation classes
• Weighted automata and logics meet computational complexity
• On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• A quantum walk-assisted approximate algorithm for bounded NP optimisation problems

This page was built for publication: Strong lower bounds on the approximability of some NPO PB-complete maximization problems

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