On fixed-parameter tractability and approximability of NP optimization problems
From MaRDI portal
Publication:1362338
DOI10.1006/JCSS.1997.1490zbMATH Open0882.68064OpenAlexW2043997666MaRDI QIDQ1362338FDOQ1362338
Authors: Liming Cai, Jianer 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
Recommendations
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Learnability and the Vapnik-Chervonenkis dimension
- Algorithms for Scheduling Independent Tasks
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Fixed-Parameter Tractability and Completeness I: Basic Results
- On the structure of parameterized problems in NP
- Title not available (Why is that?)
- On limited nondeterminism and the complexity of the V-C dimension
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Nondeterminism within $P^ * $
- Approximation properties of NP minimization classes
- Classes of bounded nondeterminism
- Title not available (Why is that?)
- On input read-modes of alternating Turing machines
- Optimization problems and the polynomial hierarchy
Cited In (29)
- Kernelization: new upper and lower bound techniques
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- The inapproximability of non-NP-hard optimization problems.
- Polynomial kernelizations for \(\text{MIN} \text{F}^+ \Pi_1\) and \(\text{MAX NP}\)
- The birth and early years of parameterized complexity
- A basic parameterized complexity primer
- A fixed-parameter-tractable algorithm for set packing
- Parameterizing above or below guaranteed values
- Capital budgeting problems: a parameterized point of view
- The complexity of speedrunning video games
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Approximate solution of NP optimization problems
- On the computational hardness based on linear fpt-reductions
- Fixed-parameter approximation: conceptual framework and approximability results
- Safe approximation and its relation to kernelization
- Bounded fixed-parameter tractability and reducibility
- Knapsack problems: a parameterized point of view
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- On the existence of subexponential parameterized algorithms
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On the structure of parameterized problems in NP
- On subexponential and FPT-time inapproximability
- Title not available (Why is that?)
- MNP: A class of NP optimization problems
- Structure of polynomial-time approximation
- Improved exact algorithms for MAX-SAT
- Fixed-Parameter and Approximation Algorithms: A New Look
- Parameterized constraint satisfaction problems: a survey
- Polynomial time approximation schemes and parameterized complexity
This page was built for publication: On fixed-parameter tractability and approximability of NP optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362338)
