On fixed-parameter tractability and approximability of NP optimization problems
From MaRDI portal
Publication:1362338
DOI10.1006/jcss.1997.1490zbMath0882.68064OpenAlexW2043997666MaRDI QIDQ1362338
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
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
