2 Search Results for "Solis-Oba, Roberto"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.78
A PTAS for Packing Hypercubes into a Knapsack

Authors: Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study the d-dimensional hypercube knapsack problem ({d}-D Hc-Knapsack) where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+ε). For d = 2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d > 2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren’s result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called 𝒱-Boxes and 𝒩-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems.
Cite as

Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas. A PTAS for Packing Hypercubes into a Knapsack. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2022.78,
  author =	{Jansen, Klaus and Khan, Arindam and Lira, Marvin and Sreenivas, K. V. N.},
  title =	{{A PTAS for Packing Hypercubes into a Knapsack}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.78},
  URN =		{urn:nbn:de:0030-drops-164192},
  doi =		{10.4230/LIPIcs.ICALP.2022.78},
  annote =	{Keywords: Multidimensional knapsack, geometric packing, cube packing, strip packing}
}
Document
DOI: 10.4230/DagSemRep.345
Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251)

Authors: Evripidis Bampis, Klaus Jansen, Giuseppe Persiano, Roberto Solis-Oba, and Gordon T. Wilfong

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Evripidis Bampis, Klaus Jansen, Giuseppe Persiano, Roberto Solis-Oba, and Gordon T. Wilfong. Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251). Dagstuhl Seminar Report 345, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{bampis_et_al:DagSemRep.345,
  author =	{Bampis, Evripidis and Jansen, Klaus and Persiano, Giuseppe and Solis-Oba, Roberto and Wilfong, Gordon T.},
  title =	{{Approximation and Randomized Algorithms in Communication Networks (Dagstuhl Seminar 02251)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{345},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.345},
  URN =		{urn:nbn:de:0030-drops-152265},
  doi =		{10.4230/DagSemRep.345},
}
  • Refine by Author
  • 2 Jansen, Klaus
  • 1 Bampis, Evripidis
  • 1 Khan, Arindam
  • 1 Lira, Marvin
  • 1 Persiano, Giuseppe
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Multidimensional knapsack
  • 1 cube packing
  • 1 geometric packing
  • 1 strip packing

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2003
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact