Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
An Approximation Algorithm for the Stack-Up Problem
MMOR 51(2): 203-233, 2000
Abstract
| We consider the combinatorial stack-up problem which is motivated by stacking up bins from a conveyor onto pallets. The stack-up problem is to decide whether a given list q of labeled objects can be processed by removing step by step one of the first s objects of q so that the following holds. After each removal there are at most p labels for which there is an object already removed from q and an object still contained in q. We introduce and analyse polynomial time approximation algorithms for the stack-up problem. |
| Key words: approximability, discrete algorithms, problem complexity, computational analysis |