On the efficiency of polynomial time approximation schemes
From MaRDI portal
Publication:290268
DOI10.1016/S0020-0190(97)00164-6zbMath1337.68125MaRDI QIDQ290268
Publication date: 1 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (35)
Chordless paths through three vertices ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Approximation schemes for the generalized extensible bin packing problem ⋮ Independent Sets in Restricted Line of Sight Networks ⋮ Fixed-parameter approximation: conceptual framework and approximability results ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Knapsack problems: a parameterized point of view ⋮ EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ Approximation schemes for packing splittable items with cardinality constraints ⋮ Batch Coloring Flat Graphs and Thin ⋮ Independent sets in Line of Sight networks ⋮ Finding Large Independent Sets in Line of Sight Networks ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Unnamed Item ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Approximation and hardness of shift-Bribery ⋮ Structure of polynomial-time approximation ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ On the computational hardness based on linear fpt-reductions ⋮ Core instances for testing: a case study ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Dynamic programming optimization in line of sight networks ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ Parameterized Complexity ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Parameterized counting problems ⋮ A tight analysis of geometric local search
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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 NP-completeness made easy
- Property testing and its connection to learning and approximation
- Computation Models for Parameterized Complexity
- Fixed-Parameter Tractability and Completeness I: Basic Results
- MAX-CUT has a randomized approximation scheme in dense graphs
This page was built for publication: On the efficiency of polynomial time approximation schemes
