Polynomial time approximation schemes and parameterized complexity
From MaRDI portal
Recommendations
Cites work
- A polynomial time approximation scheme for general multiprocessor job scheduling
- Algorithms for Scheduling Independent Tasks
- Approximation algorithms for NP-complete problems on planar graphs
- Characterizing parallel hierarchies by reducibilities
- Deciding first-order properties of locally tree-decomposable structures
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1305477 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 2080999 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- Non deterministic polynomial optimization problems and their approximations
- On fixed-parameter tractability and approximability of NP optimization problems
- On Syntactic versus Computational Views of Approximability
- On the efficiency of polynomial time approximation schemes
- Optimization, approximation, and complexity classes
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Toward a unified approach for the classification of NP-complete optimization problems
Cited in
(27)- Polynomial-average-time satisfiability problems
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- On fixed-parameter tractability and approximability of NP optimization problems
- Master-slave strategy and polynomial approximation
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Probabilistic parameterized polynomial time
- Tight worst-case bounds for polynomial loop programs
- Fixed-parameter approximation: conceptual framework and approximability results
- Knapsack problems: a parameterized point of view
- Scheduling two-stage jobs on multiple flowshops
- Sharp separation and applications to exact and parameterized algorithms
- The complexity of polynomial-time approximation
- Safe approximation and its relation to kernelization
- On the efficiency of polynomial time approximation schemes
- Parameterized complexity and subexponential-time computability
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- Fundamentals of parameterized complexity
- Polynomial-time computable approximation of families of semialgebraic sets and combinatorial complexity
- scientific article; zbMATH DE number 1335885 (Why is no real title available?)
- scientific article; zbMATH DE number 1760347 (Why is no real title available?)
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- Mathematical Foundations of Computer Science 2004
- scientific article; zbMATH DE number 2221549 (Why is no real title available?)
- Structure of polynomial-time approximation
- A problem reduction based approach to discrete optimization algorithm design
This page was built for publication: Polynomial time approximation schemes and parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q867860)
