Strong lower bounds on the approximability of some NPO PB-complete maximization problems
From MaRDI portal
Publication:3569014
DOI10.1007/3-540-60246-1_129zbMath1193.68120OpenAlexW1511100116MaRDI QIDQ3569014
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (10)
Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems ⋮ Tight approximation bounds for dominating set on graphs of bounded arboricity ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Structure in approximation classes ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ A quantum walk-assisted approximate algorithm for bounded NP optimisation problems ⋮ Unnamed Item ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
This page was built for publication: Strong lower bounds on the approximability of some NPO PB-complete maximization problems
