Sorting with Complete Networks of Stacks
| Autor: | Marco E. Lübbecke, Felix G. König |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2007 |
| Předmět: |
Discrete mathematics
hardness of approximation stack Approximation algorithm 510 Mathematik Binary logarithm Upper and lower bounds PSPACE-complete law.invention Combinatorics Permutation law Data_FILES sort Graph coloring ddc:510 Merge sort Circle graph sorting Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Algorithms and Computation ISBN: 9783540921813 ISAAC |
| DOI: | 10.14279/depositonce-14385 |
| Popis: | Knuth introduced the problem of sorting numbers using 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 this way; but they ignored the associated optimization problem (minimize the number of moves) and its complexity. Given a complete, thus cyclic, network of k ≥ 2 stacks, any permutation is obviously sortable. The important question now is how to actually sort 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 of the great practical importance of this optimization version. We show that it is NP-hard to approximate the minimum number of shuffles within $\mathcal{O}(n^{1-\epsilon})$ 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 of independent interest). For complete networks, a simple merge sort algorithm achieves an approximation ratio of $\mathcal{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 αk + 1 stacks, given an α-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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|