> Detailanzeige

Gálvez, Waldo [Verfasser:in]; Grandoni, Fabrizio [Verfasser:in]; Khan, Arindam [Verfasser:in]; Ramírez-Romero, Diego [Verfasser:in]; Wiese, Andreas [Verfasser:in] ; Waldo Gálvez and Fabrizio Grandoni and Arindam Khan and Diego Ramírez-Romero and Andreas Wiese [Mitwirkende:r]

Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht
  • Titel: Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
  • Beteiligte: Gálvez, Waldo [Verfasser:in]; Grandoni, Fabrizio [Verfasser:in]; Khan, Arindam [Verfasser:in]; Ramírez-Romero, Diego [Verfasser:in]; Wiese, Andreas [Verfasser:in]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.SoCG.2021.39
  • Schlagwörter: geometric packing ; two-dimensional knapsack ; Approximation algorithms
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+ε < 1.89 and there is a (3/2+ε)-approximation algorithm if we are allowed to rotate items by 90 degrees [Gálvez et al., FOCS 2017]. In this paper, we give (4/3+ε)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n. Gálvez et al.’s algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, we present an algorithm that computes the essentially optimal structured packing into these regions.
  • Zugangsstatus: Freier Zugang