## Abstract

An important variant of two-dimensional bin packing problem (2BP), which is also used in some approximation algorithms for its solution, is the strip packing problem (2SP), in which the items have to be packed in a strip of width W and infinite height, so as to minimize the height at which the strip is used. This chapter starts by reviewing classical mathematical models which have implications relevant to the topic of the present survey, and discuss more recent results. It devotes to upper bounds; including metaheuristics and approximation algorithms, lower bound, and exact algorithms. Most of the off-line heuristic algorithms from the literature are of the greedy type, and can be classified in two families: one-phase algorithms and two-phase algorithms. Good lower bounds on the optimal solution value are important both in the implementation of exact enumerative approaches and in the empirical evaluation of approximate solutions.

Original language | English |
---|---|

Title of host publication | Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition |

Publisher | Wiley & Blackwell |

Pages | 107-129 |

Number of pages | 23 |

ISBN (Electronic) | 9781119005353 |

ISBN (Print) | 9781848216570 |

DOIs | |

Publication status | Published - 15 Sep 2014 |

## Keywords

- Approximation algorithms
- Exact algorithms
- Lower bounds
- Metaheuristics
- Off-line heuristic algorithms
- One-phase algorithms
- Strip packing problem (2SP)
- Two-dimensional bin packing problem (2BP)
- Two-phase algorithms
- Upper bounds