A parameterized approximation scheme for the geometric knapsack problem with wide items

DOI10.4230/LIPICS.IPEC.2023.33MaRDI QIDQ6926174zbMATH OpenFDO

Authors Mathieu Mari, Timothe Picavet, Michał Pilipczuk

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.33

zbMATH Keywords

approximation schemecolor codingcomputational geometrydynamic programminggeometric knapsackparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A quasi-PTAS for the two-dimensional geometric knapsack problem
• A SHORTEST PAIR OF PATHS ON THE PLANE WITH OBSTACLES AND CROSSING AREAS
• Approximating Geometric Knapsack via L-packings
• Detecting weakly simple polygons
• Geometric folding algorithms. Linkages, origami, polyhedra
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• On rectangle packing, maximizing benefits
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

This page was built for publication: A parameterized approximation scheme for the geometric knapsack problem with wide items

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