Approximating Geometric Knapsack via L-packings

DOI10.1145/3473713MaRDI QIDQ5035877zbMATH OpenOpenAlexFDO

Authors Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Sandy Heydrich, Arindam Khan, Andreas Wiese

Publication date 22 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsrectangle packinggeometric knapsack

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• Faster approximation schemes for the two-dimensional knapsack problem
• A structural lemma in 2-dimensional packing, and its implications on approximability

Cited in

(10)

• Optimizing some constructions with bars: new geometric knapsack problems
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• Geometric Knapsack problems
• On improved interval cover mechanisms for crowdsourcing markets
• Tight approximation algorithms for geometric bin packing with skewed items
• Peak demand minimization via sliced strip packing
• (Re)packing equal disks into rectangle
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints

This page was built for publication: Approximating Geometric Knapsack via L-packings

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