The inapproximability of non-NP-hard optimization problems.

DOI10.1016/S0304-3975(01)00343-7MaRDI QIDQ1853546zbMATH OpenOpenAlexFDO

Authors Liming Cai, David W. Juedes, Iyad 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

Computational complexityCombinatorial optimizationReductionsApproximation hardness

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1775419
• On the hardness of approximating minimization problems
• scientific article; zbMATH DE number 1256636
• scientific article; zbMATH DE number 847149
• On Unapproximable Versions of $NP$-Complete Problems

Cites work

• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1332665 (Why is no real title available?)
• scientific article; zbMATH DE number 1114044 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for combinatorial problems
• Classes of bounded nondeterminism
• Efficient probabilistically checkable proofs and applications to approximations
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Nondeterminism within $P^ * $
• On finding a minimum dominating set in a tournament
• On fixed-parameter tractability and approximability of NP optimization problems
• On problems with short certificates
• On the Amount of Nondeterminism and the Power of Verifying
• On the structure of parameterized problems in NP

Cited in

(11)

• scientific article; zbMATH DE number 1839429 (Why is no real title available?)
• scientific article; zbMATH DE number 1775419 (Why is no real title available?)
• Non-approximability results for optimization problems on bounded degree instances
• A dichotomy result for Ramsey quantifiers
• Characterizing polynomial Ramsey quantifiers
• The hardness of approximation: Gap location
• A natural family of optimization problems with arbitrarily small approximation thresholds
• On the computational hardness based on linear fpt-reductions
• Fixed-parameter approximation: conceptual framework and approximability results
• An alternative approach for proving the NP-hardness of optimization problems
• Parameterized computation and complexity: a new approach dealing with NP-hardness

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

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