Sorting with Complete Networks of Stacks

Felix G. König and Marco E. Lübbecke

Algorithms and Computation: 19th International Symposium, ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pp. 896-907, Springer, 2008.

not available

stack, sorting, hardness of approximation, PSPACE-complete

Knuth introduced the problem of sorting with a sequence of stacks. Tarjan extended this idea to sorting with acyclic networks of stacks (and queues), where items to be sorted move from a source through the network to a sink while they may be stored temporarily at nodes (the stacks). Both characterized which permutations are sortable; but complexity of sorting was not an issue.

In contrast, given a complete, thus cyclic, network of k >= 2 stacks, any permutation is obviously sortable. We ask how to do the sorting with a minimum number of shuffles, i.e. moves in between stacks. This is a natural algorithmic complement to the structural questions asked by Knuth, Tarjan, and others. It is the first time shuffles are considered in stack sorting - despite their practical importance.

We show that it is NP-hard to approximate the minimum number of shuffles within O(n^1-e) for networks of k >= 4 stacks, even when the problem is restricted to complete networks, by relating stack sorting to MIN-k-PARTITION on circle graphs (for which we prove a stronger inapproximability result). For complete networks, a simple merge sort algorithm achieves an approximation ratio of O(n log n) for k >= 3; however, closing the logarithmic gap to our lower bound appears to be an intriguing open question. Yet, on the positive side, we present a tight approximation algorithm which computes a solution with a linear approximation guarantee, using a resource augmentation to ak+1 stacks, given an a-approximation algorithm for coloring circle graphs.

When there are constraints as to which items may be placed on top of each other, deciding about sortability becomes non-trivial again. We show that this problem is PSPACE-complete, for every fixed k >= 3.

Download as [PDF] [ps]