Sie sind hier

# Preprints 2008

Zitatschlüssel Report-036-2007 König, Felix G. and Lübbecke, Marco E. 2007 Stra\ 036 January Algorithms and Computation: 19th International Symposium, ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pp. 896-907, Springer-Verlag, 2008. Technische Universität Berlin, Institut für Mathematik 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 = 036, 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 = 036, 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. Preprint