Approximating Geometric Knapsack via L-packings

DOI10.1145/3473713OpenAlexW3203979862MaRDI QIDQ5035877FDOQ5035877

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

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

zbMATH Keywords

approximation algorithmsrectangle packinggeometric knapsack

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (10)

• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Optimizing some constructions with bars: new geometric knapsack problems
• 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)