The inapproximability of non-NP-hard optimization problems.

DOI10.1016/S0304-3975(01)00343-7zbMath1061.68059OpenAlexW2062172380MaRDI QIDQ1853546

David W. Juedes, Li-Ming Cai, Iyad A. Kanj

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00343-7

zbMATH Keywords

Combinatorial optimizationComputational complexityReductionsApproximation hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Fixed-parameter approximation: conceptual framework and approximability results ⋮ A Dichotomy Result for Ramsey Quantifiers ⋮ Characterizing polynomial Ramsey quantifiers ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ On the computational hardness based on linear fpt-reductions ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finding a minimum dominating set in a tournament
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for combinatorial problems
• On problems with short certificates
• On fixed-parameter tractability and approximability of NP optimization problems
• On the structure of parameterized problems in NP
• Classes of bounded nondeterminism
• Nondeterminism within $P^ * $
• On the Amount of Nondeterminism and the Power of Verifying
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Efficient probabilistically checkable proofs and applications to approximations

This page was built for publication: The inapproximability of non-NP-hard optimization problems.