Article ID: | iaor2014174 |
Volume: | 27 |
Issue: | 1 |
Start Page Number: | 115 |
End Page Number: | 131 |
Publication Date: | Jan 2014 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Reinelt Gerhard, Bksi Jzsef, Galambos Gbor, Balogh Jnos |
Keywords: | bin packing |
Semi‐on‐line algorithms for the bin‐packing problem allow, in contrast to pure on‐line algorithms, the use of certain types of additional operations for each step. Examples include repacking, reordering or lookahead before packing the items. Here we define and analyze a semi‐on‐line algorithm where for each step at most