NDLI: Packing 2-dimensional bins in harmony

Content Provider	IEEE Xplore Digital Library
Author	Caprara, A.
Copyright Year	2002
Description	Author affiliation: Dipt. di Elettronica, Inf. e Sistemistica, Bologna Univ., Italy (Caprara, A.)
Abstract	We consider 2-Dimensional (Finite) Bin Packing (2BP), which is one of the most important generalizations of the well-known Bin Packing (BP) and calls for orthogonally packing a given set of rectangles (that cannot be rotated) into the minimum number of unit size squares. There are many open questions concerning the approximability of 2BP, whereas the situation for the 2-stage case, in which the items must first be packed into shelves that are then packed into bins, is essentially settled. For this reason, we study the asymptotic worst-case ratio between the optimal solution values of the 2-stage and general 2BP, showing that it is equal to T/sub /spl infin//=1.691..., the well-known worst-case ratio of the Harmonic algorithm for BP. This ratio is achieved by packing the items into shelves by decreasing heights as in the Harmonic algorithm and then optimally packing the resulting shelves into bins. This immediately yields polynomial time approximation algorithms for 2BP whose asymptotic worst-case ratio is arbitrarily close to T/sub /spl infin//, i.e. substantially smaller than 2+/spl epsi/, that was the best ratio achievable so far and constituted the first (recent) improvement over the 2.125 ratio shown in the early 80s. In particular, we manage to push the approximability threshold below 2, which is often a critical value in approximation. The main idea in our analysis is to use the fact that the fractional and integer BP solutions have almost the same value, which is implicit in the approximation schemes for the problem, as a stand-alone structural result. This implies the existence of modified heights for the shelves whose sum yields approximately the number of bins needed to pack them. With this in mind, our proof can easily be adapted to different cases. For instance, we can derive new upper bounds on the worst-case ratio of several shelf heuristics for 2BP, among which a bound of (17/10)(11/9)=2.077... (rather than 2.125) on the 20-years-lasting champion mentioned above. Moreover, we can easily derive the asymptotic worst-case ratio between the 2-stage and general 2BP solution values as a function of the maximum width of the rectangles, showing that this ratio is independent of the maximum height. Finally, under a conjecture that appears to be supported by experimental evidence, we show that our main heuristic has an asymptotic worst-case ratio in the interval (1.490,1.507) when all the rectangles to be packed are squares. This would improve the current best worst-case ratio of 14/9=1.555... for this special case.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Maht. Found. Comput. (TCMF) ACM/SIGACT
Starting Page	490
Ending Page	499
File Size	396971
Page Count	10
File Format	PDF
ISBN	0769518222
ISSN	02725428
DOI	10.1109/SFCS.2002.1181973
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-11-19
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Approximation algorithms Strips Upper bound Computer science
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Branch and Bound Algorithm for solving the 2D Strip Packing Problem

A Parallel Algorithm for 2D Square Packing

Approximating Bin Packing within O(log OPT * Log Log OPT) Bins

Multi-Tiered Algorithms for 2-Dimensional Bin Packing

Rounding in ϵ-approximation algorithms

Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem

Improved upper bound for sorting by short swaps

On Allocating Goods to Maximize Fairness

Approximation guarantees for fictitious play

Packing 2-dimensional bins in harmony

Similar Documents

A Branch and Bound Algorithm for solving the 2D Strip Packing Problem

A Parallel Algorithm for 2D Square Packing

Approximating Bin Packing within O(log OPT * Log Log OPT) Bins

Multi-Tiered Algorithms for 2-Dimensional Bin Packing

Rounding in ϵ-approximation algorithms

Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem

Improved upper bound for sorting by short swaps

On Allocating Goods to Maximize Fairness

Approximation guarantees for fictitious play

Packing 2-dimensional bins in harmony