Approximating bounded degree instances of NP-hard problems

DOI10.1007/3-540-44669-9_4MaRDI QIDQ4782694zbMATH OpenFDO

Authors Marek Karpinski

Publication date 2 December 2002

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2138/21380024

zbMATH Keywords

bounded degree combinatorial optimizationcomputational complexityexplicit nonapproximability bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Complexity of approximating bounded variants of optimization problems
• Inapproximability results for bounded variants of optimization problems.
• Non-approximability results for optimization problems on bounded degree instances
• Approximation hardness of dominating set problems in bounded degree graphs
• The inapproximability of non-NP-hard optimization problems.

Cited in

(6)

• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• On the approximability of Dodgson and Young elections
• Towards better inapproximability bounds for TSP: a challenge of global dependencies
• Approximation hardness for small occurrence instances of NP-hard problems
• Non-approximability results for optimization problems on bounded degree instances
• Maximum-cover source location problems with objective edge-connectivity three

This page was built for publication: Approximating bounded degree instances of NP-hard problems

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