On fixed-parameter tractability and approximability of NP optimization problems
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- Algorithms for Scheduling Independent Tasks
- Approximation properties of NP minimization classes
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Classes of bounded nondeterminism
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Learnability and the Vapnik-Chervonenkis dimension
- Nondeterminism within $P^ * $
- On input read-modes of alternating Turing machines
- On limited nondeterminism and the complexity of the V-C dimension
- On the structure of parameterized problems in NP
- Optimization problems and the polynomial hierarchy
- Optimization, approximation, and complexity classes
Cited in
(28)- The inapproximability of non-NP-hard optimization problems.
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Bounded fixed-parameter tractability and reducibility
- Parameterized constraint satisfaction problems: a survey
- Structure of polynomial-time approximation
- On the structure of parameterized problems in NP
- Improved exact algorithms for MAX-SAT
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Knapsack problems: a parameterized point of view
- The complexity of speedrunning video games
- Capital budgeting problems: a parameterized point of view
- Fixed-parameter approximation: conceptual framework and approximability results
- MNP: A class of NP optimization problems
- Kernelization: new upper and lower bound techniques
- The birth and early years of parameterized complexity
- On the existence of subexponential parameterized algorithms
- Polynomial kernelizations for \(\text{MIN} \text{F}^+ \Pi_1\) and \(\text{MAX NP}\)
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Approximate solution of NP optimization problems
- Fixed-Parameter and Approximation Algorithms: A New Look
- On the computational hardness based on linear fpt-reductions
- A basic parameterized complexity primer
- A fixed-parameter-tractable algorithm for set packing
- Parameterizing above or below guaranteed values
- Polynomial time approximation schemes and parameterized complexity
- Safe approximation and its relation to kernelization
- scientific article; zbMATH DE number 847149 (Why is no real title available?)
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
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)
