Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

DOI10.4230/LIPICS.ESA.2019.53MaRDI QIDQ5075797zbMATH OpenOpenAlexFDO

Authors Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1906.10982

zbMATH Keywords

geometric knapsackindependent set of rectanglesparameterized approximationparameterized intractability

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Faster approximation schemes for the two-dimensional knapsack problem
• Approximating Geometric Knapsack via L-packings

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• A Polynomial Time Approximation Scheme for the Square Packing Problem
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Algorithms – ESA 2005
• Approximating Geometric Knapsack via L-packings
• Approximation algorithms for maximum independent set of pseudo-disks
• Consensus patterns (probably) has no EPTAS
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster approximation schemes for the two-dimensional knapsack problem
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• Fixed-Parameter Approximation: Conceptual Framework and Approximability 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
• Lossy kernelization
• Lower bounds for approximation schemes for Closest String
• Maximum independent set of rectangles
• On Parameterized Approximability
• On rectangle packing, maximizing benefits
• On the efficiency of polynomial time approximation schemes
• Optimal packing and covering in the plane are NP-complete
• Parameterized approximability of maximizing the spread of influence in networks
• Parameterized Approximation Problems
• Parameterized Approximation Schemes Using Graph Widths
• Parameterized approximation via fidelity preserving transformations
• Parameterized approximations via d-skew-symmetric multicut
• Parameterized inapproximability of degree anonymization
• Parameterized inapproximability of target set selection and generalizations
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• The constant inapproximability of the parameterized dominating set problem

Cited in

(6)

• Robust online algorithms for dynamic choosing problems
• Approximating the maximum independent set of convex polygons with a bounded number of directions
• Kernelization of counting problems
• A parameterized approximation scheme for the geometric knapsack problem with wide items
• Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
• Parameterized approximation for maximum weight independent set of rectangles and segments

This page was built for publication: Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075797)