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

DOI10.1007/3-540-60246-1_129zbMATH Open1193.68120OpenAlexW1511100116MaRDI QIDQ3569014FDOQ3569014

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

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

Mathematics Subject Classification ID

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

Cited In (11)

• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Structure in approximation classes
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• Time-approximation trade-offs for inapproximable problems
• 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
• Title not available (Why is that?)

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)