@techreport{Report-036-2007,
Title = {Sorting with Complete Networks of Stacks},
Author = {K\"onig, Felix G. and L\"ubbecke, Marco E.},
Year = {2007},
Address = {Stra\},
Number = {036},
Month = {January},
Note = {Algorithms and Computation: 19th International Symposium, ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pp. 896-907, Springer-Verlag, 2008.},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
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 {\it sortable}; but complexity of sorting was not an issue. In contrast, given a complete, thus cyclic, network of {\it 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 {\it k >= 4} stacks, even when the problem is restricted to complete networks, by relating stack sorting to {\it 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 {\it O(n log n)} for {\it 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 {\it ak+1} stacks, given an {\it 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 {\it k >= 3}.},
Url = {http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2007/Report-036-2007.pdf},
Keywords = {stack, sorting, hardness of approximation, PSPACE-complete}
}