An approximation algorithm for the stack-up problem

We consider the combinatorial stack-up problem 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 the first object is already removed from q and the last object is still contained in q. We give some NP-completeness results and we introduce and analyze a polynomial time approximation algorithm for the stack-up problem. Manuscript received: January 1999/final version received: August 1999