Khan, Arindam ;
Sharma, Eklavya
Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items
Abstract
In the Twodimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axisaligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is 1.406 by Bansal and Khan [SODA'14]. A wellstudied variant of the problem is Guillotine Twodimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of endtoend axisparallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let λ be the smallest constant such that for every set I of items, the number of bins in the optimal solution to G2BP for I is upper bounded by λ opt(I) + c, where opt(I) is the number of bins in the optimal solution to 2BP for I and c is a constant. It is known that 4/3 ≤ λ ≤ 1.692. Bansal and Khan [SODA'14] conjectured that λ = 4/3. The conjecture, if true, will imply a (4/3+ε)approximation algorithm for 2BP. According to convention, for a given constant δ > 0, a rectangle is large if both its height and width are at least δ, and otherwise it is called skewed. We make progress towards the conjecture by showing λ = 4/3 for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on λ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS.
BibTeX  Entry
@InProceedings{khan_et_al:LIPIcs.APPROX/RANDOM.2021.22,
author = {Khan, Arindam and Sharma, Eklavya},
title = {{Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {22:122:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14715},
URN = {urn:nbn:de:0030drops147151},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.22},
annote = {Keywords: Geometric bin packing, guillotine separability, approximation algorithms}
}
15.09.2021
Keywords: 

Geometric bin packing, guillotine separability, approximation algorithms 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Issue date: 

2021 
Date of publication: 

15.09.2021 