Worst-case analysis of the subset sum algorithm for bin packing |
| |
| Authors: | Alberto Caprara Ulrich Pferschy |
| |
| Institution: | a DEIS, Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, Viale Risorgimento 2, I-40136 Bologna, Italy
b Department of Statistics and Operations Research, University of Graz, Universitaetsstr. 15, A-8010 Graz, Austria |
| |
| Abstract: | We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. We show a nontrivial upper bound on this ratio of  , almost matching a known lower bound. |
| |
| Keywords: | Bin packing Subset sum heuristic Worst-case analysis |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
