Lower bounds and reduction procedures for the bin packing problem. Martello, S. & Toth, P. Discrete Applied Mathematics, 28:59--70, 1990.
Lower bounds and reduction procedures for the bin packing problem [link]Paper  doi  abstract   bibtex   
The bin packing problem, in which a set of items of various sizes has to be packed into a minimum number of identical bins, has been extensively studied during the past fifteen years, mainly with the aim of finding fast heuristic algorithms to provide good approximate solutions. We present lower bounds and a dominance criterion and derive a reduction algorithm. Lower bounds are evaluated through an extension of the concept of worst-case performance. For both lower bounds and reduction algorithm an experimental analysis is provided.
@article{martello_lower_1990,
	title = {Lower bounds and reduction procedures for the bin packing problem},
	volume = {28},
	issn = {0166-218X},
	url = {http://www.sciencedirect.com/science/article/B6TYW-45TK910-8/2/c9a86673ae8bcb8f45db624306877c4f},
	doi = {10.1016/0166-218X(90)90094-S},
	abstract = {The bin packing problem, in which a set of items of various sizes has to be packed into a minimum number of identical bins, has been extensively studied during the past fifteen years, mainly with the aim of finding fast heuristic algorithms to provide good approximate solutions. We present lower bounds and a dominance criterion and derive a reduction algorithm. Lower bounds are evaluated through an extension of the concept of worst-case performance. For both lower bounds and reduction algorithm an experimental analysis is provided.},
	urldate = {2010-10-01TZ},
	journal = {Discrete Applied Mathematics},
	author = {Martello, S. and Toth, P.},
	year = {1990},
	keywords = {Bin packing problem, dominance criterion, lower bound, reduction algorithm, worst-case performance},
	pages = {59--70}
}
Downloads: 0