On the efficiency of polynomial time approximation schemes
From MaRDI portal
Recommendations
- Structure of polynomial-time approximation
- The complexity of polynomial-time approximation
- Polynomial time approximation schemes and parameterized complexity
- Mathematical Foundations of Computer Science 2004
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
Cites work
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- scientific article; zbMATH DE number 578252 (Why is no real title available?)
- scientific article; zbMATH DE number 1163704 (Why is no real title available?)
- Computation Models for Parameterized Complexity
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- MAX-CUT has a randomized approximation scheme in dense graphs
- Max NP-completeness made easy
- Property testing and its connection to learning and approximation
Cited in
(42)- A unified framework for designing EPTAS for load balancing on parallel machines
- Parameterized counting problems
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- Approximation of minimum weight spanners for sparse graphs
- Dynamic programming optimization in line of sight networks
- Structure of polynomial-time approximation
- EPTAS for load balancing problem on parallel machines with a non-renewable resource
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Batch Coloring Flat Graphs and Thin
- Knapsack problems: a parameterized point of view
- Approximation schemes for the generalized extensible bin packing problem
- EPTAS for load balancing problem on parallel machines with a non-renewable resource
- A tight analysis of geometric local search
- Fixed-parameter approximation: conceptual framework and approximability results
- Scheduling with cardinality dependent unavailability periods
- Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
- Mathematical Foundations of Computer Science 2004
- The complexity of polynomial-time approximation
- Algorithms – ESA 2005
- Parameterized complexity of machine scheduling: 15 open problems
- Independent sets in Line of Sight networks
- Improved approximations for hard optimization problems via problem instance classification
- Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- Chordless paths through three vertices
- EPTAS for the dual of splittable bin packing with cardinality constraint
- Independent Sets in Restricted Line of Sight Networks
- A much better polynomial time approximation of consistency in the LR calculus
- On the computational hardness based on linear fpt-reductions
- Approximation schemes for packing splittable items with cardinality constraints
- Parameterized complexity: the main ideas and connections to practical computing
- Fixed-parameter algorithms for unsplittable flow cover
- A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
- Local search strikes again: PTAS for variants of geometric covering and packing
- Core instances for testing: a case study
- Polynomial time approximation schemes and parameterized complexity
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- scientific article; zbMATH DE number 1496577 (Why is no real title available?)
- Safe approximation and its relation to kernelization
- Finding large independent sets in line of sight networks
- EPTAS for parallel identical machine scheduling with time restrictions
- Approximation and hardness of shift-bribery
- An efficient polynomial time approximation scheme for load balancing on uniformly related machines
This page was built for publication: On the efficiency of polynomial time approximation schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290268)
