Min-Sum Bin Packing

Leah Epstein (), David S. Johnson and Asaf Levin ()
Additional contact information
Leah Epstein: University of Haifa
David S. Johnson: AT&T Labs - Research
Asaf Levin: The Technion

Journal of Combinatorial Optimization, 2018, vol. 36, issue 2, No 11, 508-531

Abstract: Abstract We study min-sum bin packing (MSBP). This is a bin packing problem, where the cost of an item is the index of the bin into which it is packed. The problem is equivalent to a batch scheduling problem we define, where the total completion time is to be minimized. The problem is NP-hard in the strong sense. We show that it is not harder than this by designing a polynomial time approximation scheme for it. We also show that several natural algorithms which are based on well-known bin packing heuristics (such as First Fit Decreasing) fail to achieve an asymptotic finite approximation ratio, whereas Next Fit Increasing has an absolute approximation ratio of at most 2, and an asymptotic approximation ratio of at most 1.6188. We design a new heuristic that applies Next Fit Increasing on the relatively small items and adds the larger items using First Fit Decreasing, and show that its asymptotic approximation ratio is at most 1.5604.

Keywords: Bin packing; Approximation algorithms; Analysis of algorithms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0310-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-018-0310-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0310-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().