On fixed-parameter tractability and approximability of NP optimization problems
type: Item
instance of: scholarly article
title: On fixed-parameter tractability and approximability of NP optimization problems
zbMATH Open document ID: 0882.68064
published in: Journal of Computer and System Sciences
publication date: 1997-08-03T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1042932
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: NP optimization problems
author: Liming Cai
author: Jianer Chen
MaRDI profile type: Publication
full work available at URL: jcss.1997.1490
OpenAlex ID: W2043997666
cites work: Q4281539
cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
cites work: Q4230322
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: Nondeterminism within $P^ * $
cites work: On input read-modes of alternating Turing machines
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: Q4198056
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximation properties of NP minimization classes
cites work: Optimization problems and the polynomial hierarchy
cites work: Optimization, approximation, and complexity classes
cites work: On limited nondeterminism and the complexity of the V-C dimension
cites work: Algorithms for Scheduling Independent Tasks
DOI: 10.1006/JCSS.1997.1490
description: scientific article; zbMATH DE number 1042932