Preprint 036-2007

Title
Sorting with Complete Networks of Stacks
Authors
Felix G. König and Marco E. Lübbecke
Publication
Algorithms and Computation: 19th International Symposium, ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pp. 896-907, Springer, 2008.
Classification
not available
Keywords
stack, sorting, hardness of approximation, PSPACE-complete
Abstract
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(n1-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.
Source
Download as [PDF] [ps]