On fixed-parameter tractability and approximability of NP optimization problems

DOI10.1006/jcss.1997.1490zbMath0882.68064OpenAlexW2043997666MaRDI QIDQ1362338

Li-Ming Cai, Jian'er Chen

Publication date: 3 August 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1490

zbMATH Keywords

fixed-parameter tractabilityNP optimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the existence of subexponential parameterized algorithms, Improved exact algorithms for MAX-SAT, Safe Approximation and Its Relation to Kernelization, Fixed-parameter approximation: conceptual framework and approximability results, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Bounded fixed-parameter tractability and reducibility, Polynomial time approximation schemes and parameterized complexity, The complexity of speedrunning video games, Knapsack problems: a parameterized point of view, Unnamed Item, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., Structure of polynomial-time approximation, On the computational hardness based on linear fpt-reductions, A fixed-parameter-tractable algorithm for set packing, Parameterizing above or below guaranteed values, Capital Budgeting Problems: A Parameterized Point of View, Kernelization: New Upper and Lower Bound Techniques, Parameterized computation and complexity: a new approach dealing with NP-hardness, The inapproximability of non-NP-hard optimization problems., On subexponential and FPT-time inapproximability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On input read-modes of alternating Turing machines
• Optimization problems and the polynomial hierarchy
• Optimization, approximation, and complexity classes
• On limited nondeterminism and the complexity of the V-C dimension
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Approximation properties of NP minimization classes
• On the structure of parameterized problems in NP
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Classes of bounded nondeterminism
• Learnability and the Vapnik-Chervonenkis dimension
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Nondeterminism within $P^ * $
• Fixed-Parameter Tractability and Completeness I: Basic Results