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

Approximation hardnessCombinatorial optimizationComputational complexityReductions

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(12)

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

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)