License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.22
URN: urn:nbn:de:0030-drops-188470
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18847/
Go to the corresponding LIPIcs Volume Portal

Doron-Arad, Ilan ; Kulik, Ariel ; Shachnai, Hadas

An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding

pdf-format:
LIPIcs-APPROX22.pdf (0.9 MB)

Abstract

We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in [0,1], and a partition matroid over the items. The goal is to pack the items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. This variant of classic Bin Packing has natural applications in secure storage on the Cloud, as well as in equitable scheduling and clustering with fairness constraints.
Our main result is an asymptotic fully polynomial-time approximation scheme (AFPTAS) for Bin Packing with a partition matroid constraint. This scheme generalizes the known AFPTAS for Bin Packing with Cardinality Constraints and improves the existing asymptotic polynomial-time approximation scheme (APTAS) for Group Bin Packing, which are both special cases of Bin Packing with partition matroid. We derive the scheme via a new method for rounding a (fractional) solution for a configuration-LP. Our method uses this solution to obtain prototypes, in which items are interpreted as placeholders for other items, and applies fractional grouping to modify a fractional solution (prototype) into one having desired integrality properties.

BibTeX - Entry

@InProceedings{doronarad_et_al:LIPIcs.APPROX/RANDOM.2023.22,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
  title =	{{An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18847},
  URN =		{urn:nbn:de:0030-drops-188470},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.22},
  annote =	{Keywords: bin packing, partition-matroid, AFPTAS, LP-rounding}
}

Keywords: bin packing, partition-matroid, AFPTAS, LP-rounding
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI