Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.4523
Fulltext available Open Access
DC FieldValueLanguage
dc.contributor.authorKulik, Ariel-
dc.contributor.authorMnich, Matthias-
dc.contributor.authorShachnai, Hadas-
dc.date.accessioned2022-06-17T11:40:24Z-
dc.date.available2022-06-17T11:40:24Z-
dc.date.issued2022-05-25-
dc.identifier.citationarXiv:2205.12828 (2022)de_DE
dc.identifier.urihttp://hdl.handle.net/11420/12921-
dc.description.abstractWe study the 22-Dimensional Vector Bin Packing Problem (2VBP), a generalization of classic Bin Packing that is widely applicable in resource allocation and scheduling. In 2VBP we are given a set of items, where each item is associated with a two-dimensional volume vector. The objective is to partition the items into a minimal number of subsets (bins), such that the total volume of items in each subset is at most 11 in each dimension. We give an asymptotic (43+e)\left(\frac{4}{3}+\varepsilon\right)-approximation for the problem, thus improving upon the best known asymptotic ratio of (1+ln32+e)˜1.406\left(1+\ln \frac{3}{2}+\varepsilon\right)\approx 1.406 due to Bansal, Elias and Khan (SODA 2016). Our algorithm applies a novel Round&Round approach which iteratively solves a configuration LP relaxation for the residual instance and samples a small number of configurations based on the solution for the configuration LP. For the analysis we derive an iteration-dependent upper bound on the solution size for the configuration LP, which holds with high probability. To facilitate the analysis, we introduce key structural properties of 2VBP instances, leveraging the recent fractional grouping technique of Fairstein et al. (ESA 2021).en
dc.language.isoende_DE
dc.rightsCopyrightde_DE
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/de_DE
dc.subject.ddc510: Mathematikde_DE
dc.titleAn asymptotic (4/3+epsilon)-approximation for the 2-dimensional vector bin packing problemde_DE
dc.typePreprintde_DE
dc.identifier.doi10.15480/882.4523-
dc.type.dinipreprint-
dcterms.DCMITypeText-
tuhh.identifier.urnurn:nbn:de:gbv:830-882.0188460-
tuhh.oai.showtruede_DE
tuhh.abstract.englishWe study the 22-Dimensional Vector Bin Packing Problem (2VBP), a generalization of classic Bin Packing that is widely applicable in resource allocation and scheduling. In 2VBP we are given a set of items, where each item is associated with a two-dimensional volume vector. The objective is to partition the items into a minimal number of subsets (bins), such that the total volume of items in each subset is at most 11 in each dimension. We give an asymptotic (43+e)\left(\frac{4}{3}+\varepsilon\right)-approximation for the problem, thus improving upon the best known asymptotic ratio of (1+ln32+e)˜1.406\left(1+\ln \frac{3}{2}+\varepsilon\right)\approx 1.406 due to Bansal, Elias and Khan (SODA 2016). Our algorithm applies a novel Round&Round approach which iteratively solves a configuration LP relaxation for the residual instance and samples a small number of configurations based on the solution for the configuration LP. For the analysis we derive an iteration-dependent upper bound on the solution size for the configuration LP, which holds with high probability. To facilitate the analysis, we introduce key structural properties of 2VBP instances, leveraging the recent fractional grouping technique of Fairstein et al. (ESA 2021).de_DE
tuhh.publisher.urlhttps://arxiv.org/abs/2205.12828-
tuhh.publication.instituteAlgorithmen und Komplexität E-11de_DE
tuhh.identifier.doi10.15480/882.4523-
tuhh.type.opusPreprint (Vorabdruck)-
tuhh.gvk.hasppnfalse-
tuhh.hasurnfalse-
dc.type.driverpreprint-
dc.type.casraiOther-
dc.rights.nationallicensefalsede_DE
dc.identifier.arxiv2205.12828de_DE
local.status.inpressfalsede_DE
local.publisher.peerreviewedfalsede_DE
datacite.resourceTypeOther-
datacite.resourceTypeGeneralPreprint-
item.languageiso639-1en-
item.grantfulltextopen-
item.creatorOrcidKulik, Ariel-
item.creatorOrcidMnich, Matthias-
item.creatorOrcidShachnai, Hadas-
item.mappedtypePreprint-
item.creatorGNDKulik, Ariel-
item.creatorGNDMnich, Matthias-
item.creatorGNDShachnai, Hadas-
item.fulltextWith Fulltext-
item.openairetypePreprint-
item.openairecristypehttp://purl.org/coar/resource_type/c_816b-
item.cerifentitytypePublications-
crisitem.author.deptAlgorithmen und Komplexität E-11-
crisitem.author.orcid0000-0002-4721-5354-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik-
Appears in Collections:Publications with fulltext
Files in This Item:
File Description SizeFormat
2205.12828.pdf609,43 kBAdobe PDFView/Open
Thumbnail
Show simple item record

Page view(s)

43
checked on Aug 8, 2022

Download(s)

2
checked on Aug 8, 2022

Google ScholarTM

Check

Note about this record

Cite this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.