Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
From MaRDI portal
Publication:5075797
DOI10.4230/LIPIcs.ESA.2019.53OpenAlexW2978915811MaRDI QIDQ5075797
Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese
Publication date: 11 May 2022
Full work available at URL: https://arxiv.org/abs/1906.10982
parameterized approximationparameterized intractabilitygeometric knapsackindependent set of rectangles
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Approximation algorithms for maximum independent set of pseudo-disks
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Optimal packing and covering in the plane are NP-complete
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Parameterized approximability of maximizing the spread of influence in networks
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Parameterized Approximation via Fidelity Preserving Transformations
- Parameterized Approximations via d-Skew-Symmetric Multicut
- Parameterized Inapproximability of Degree Anonymization
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Consensus Patterns (Probably) Has no EPTAS
- A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- A Polynomial Time Approximation Scheme for the Square Packing Problem
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Faster approximation schemes for the two-dimensional knapsack problem
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- Lossy kernelization
- Approximating Geometric Knapsack via L-packings
- Parameterized Approximation Schemes Using Graph Widths
- Parameterized Inapproximability of Target Set Selection and Generalizations
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem
- Lower Bounds for Approximation Schemes for Closest String
- Algorithms – ESA 2005
This page was built for publication: Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
