The inapproximability of non-NP-hard optimization problems.
type: Item
instance of: scholarly article
title: The inapproximability of non-NP-hard optimization problems.
zbMATH Open document ID: 1061.68059
DOI: 10.1016/S0304-3975(01)00343-7
published in: Theoretical Computer Science
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1857079
zbMATH Keywords: Computational complexity
zbMATH Keywords: Approximation hardness
zbMATH Keywords: Combinatorial optimization
zbMATH Keywords: Reductions
author: Liming Cai
author: David W. Juedes
author: Iyad Kanj
MaRDI profile type: Publication
cites work: Q4230322
cites work: Q4230321
cites work: Q4258216
cites work: Efficient probabilistically checkable proofs and applications to approximations
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Nondeterminism within $P^ * $
cites work: On fixed-parameter tractability and approximability of NP optimization problems
cites work: On the Amount of Nondeterminism and the Power of Verifying
cites work: On the structure of parameterized problems in NP
cites work: Classes of bounded nondeterminism
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Q4850549
cites work: On problems with short certificates
cites work: Q4259986
cites work: Q4375813
cites work: Approximation algorithms for combinatorial problems
cites work: On finding a minimum dominating set in a tournament
full work available at URL: s0304-3975(01)00343-7
OpenAlex ID: W2062172380
description: scientific article; zbMATH DE number 1857079