NDLI: Absolute approximation ratios for packing rectangles into bins

Content Provider	Springer Nature Link
Author	Harren, Rolf Stee, Rob
Copyright Year	2009
Abstract	We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided $\mathcal{P}\not=\mathcal{NP}$ . For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung et al. (SIAM J. Algebr. Discrete Methods 3(1):66–76, 1982) and whose running time is slightly better than the running time of Zhang’s previously known 3-approximation algorithm (Zhang in Oper. Res. Lett. 33(2):121–126, 2005).
Starting Page	63
Ending Page	75
Page Count	13
File Format	PDF
ISSN	10946136
Journal	Journal of Scheduling
Volume Number	15
Issue Number	1
e-ISSN	10991425
Language	English
Publisher	Springer US
Publisher Date	2009-04-25
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Bin packing Rectangle packing Approximation algorithm Absolute worst-case ratio Artificial Intelligence (incl. Robotics) Production/Logistics/Supply Chain Calculus of Variations and Optimal Control; Optimization Operations Research/Decision Theory Optimization
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Management Science and Operations Research Engineering Software

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

Absolute approximation ratios for packing rectangles into bins

A new variable-sized bin packing problem

Comparing online algorithms for bin packing problems

Batched bin packing revisited

Approximation Algorithms for Extensible Bin Packing

Time-hierarchical scheduling : A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem

Open-shop dense schedules: properties and worst-case performance ratio

Stee. Absolute approximation ratios for packing rectangles into bins (2009)

Dynamic supply chain scheduling

Absolute approximation ratios for packing rectangles into bins

Similar Documents

Absolute approximation ratios for packing rectangles into bins

A new variable-sized bin packing problem

Comparing online algorithms for bin packing problems

Batched bin packing revisited

Approximation Algorithms for Extensible Bin Packing

Time-hierarchical scheduling : A worst case analysis of a hierarchical approach integrating planning and scheduling in an online problem

Open-shop dense schedules: properties and worst-case performance ratio

Stee. Absolute approximation ratios for packing rectangles into bins (2009)

Dynamic supply chain scheduling

Absolute approximation ratios for packing rectangles into bins