An Improved Algorithm for Optimal Bin Packing
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1252-1257.
Abstract
Given a set of numbers, and a set of bins of fixed capacity, the NP-complete problem of bin packing is to find the minimum number of bins needed to contain the numbers, such that the sum of the numbers assigned to each bin does not exceed the bin capacity. We present two improvements to our previous bin-completion algorithm. The first speeds up the constant factor per node generation, and the second prunes redundant parts of the search tree. The resulting algorithm appears to be asymptotically faster than our original algorithm. On problems with 90 elements, it runs over 14 times faster. Furthermore, the ratios of node generations and running times both increase with increasing problem size.
@inproceedings{ijcai2003p178,
title = {An Improved Algorithm for Optimal Bin Packing},
author = {Korf, Richard E.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1252--1257},
year = {2003},
url = {https://ijcai.org/proceedings/2003/178},
}
TY - CPAPER TI - An Improved Algorithm for Optimal Bin Packing AU - Korf, Richard E. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1252 EP - 1257 UR - https://ijcai.org/proceedings/2003/178 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
