Lower bounds and reduction procedures for the bin packing problem. Martello, S. & Toth, P. Discrete Applied Mathematics, 28:59--70, 1990. 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
{"_id":"zZkBqzQBeCfffqYRj","bibbaseid":"martello-toth-lowerboundsandreductionproceduresforthebinpackingproblem-1990","downloads":0,"creationDate":"2016-12-19T20:50:58.735Z","title":"Lower bounds and reduction procedures for the bin packing problem","author_short":["Martello, S.","Toth, P."],"year":1990,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","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":[{"propositions":[],"lastnames":["Martello"],"firstnames":["S."],"suffixes":[]},{"propositions":[],"lastnames":["Toth"],"firstnames":["P."],"suffixes":[]}],"year":"1990","keywords":"Bin packing problem, dominance criterion, lower bound, reduction algorithm, worst-case performance","pages":"59--70","bibtex":"@article{martello_lower_1990,\n\ttitle = {Lower bounds and reduction procedures for the bin packing problem},\n\tvolume = {28},\n\tissn = {0166-218X},\n\turl = {http://www.sciencedirect.com/science/article/B6TYW-45TK910-8/2/c9a86673ae8bcb8f45db624306877c4f},\n\tdoi = {10.1016/0166-218X(90)90094-S},\n\tabstract = {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.},\n\turldate = {2010-10-01TZ},\n\tjournal = {Discrete Applied Mathematics},\n\tauthor = {Martello, S. and Toth, P.},\n\tyear = {1990},\n\tkeywords = {Bin packing problem, dominance criterion, lower bound, reduction algorithm, worst-case performance},\n\tpages = {59--70}\n}\n\n","author_short":["Martello, S.","Toth, P."],"key":"martello_lower_1990","id":"martello_lower_1990","bibbaseid":"martello-toth-lowerboundsandreductionproceduresforthebinpackingproblem-1990","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/B6TYW-45TK910-8/2/c9a86673ae8bcb8f45db624306877c4f"},"keyword":["Bin packing problem","dominance criterion","lower bound","reduction algorithm","worst-case performance"],"downloads":0,"html":""},"search_terms":["lower","bounds","reduction","procedures","bin","packing","problem","martello","toth"],"keywords":["bin packing problem","dominance criterion","lower bound","reduction algorithm","worst-case performance"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}