Document Open Access Logo

On Sorting with a Network of Two Stacks

Authors Matúš Mihalák , Marc Pont

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2019.3.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Matúš Mihalák
  • Department of Data Science and Knowledge Engineering, Maastricht University, The Netherlands
Marc Pont
  • Department of Data Science and Knowledge Engineering, Maastricht University, The Netherlands

Acknowledgements

The authors would like to thank Peter Widmayer and Thomas Erlebach for fruitful discussions on the topic.

Cite As Get BibTex

Matúš Mihalák and Marc Pont. On Sorting with a Network of Two Stacks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.ATMOS.2019.3

Abstract

Sorting with stacks is a collection of problems that deal with sorting a sequence of numbers by pushing and popping the numbers to and from a given set of stacks. Multiple concrete decision or optimization questions are formed by restricting the access to the stacks. The motivation comes, e.g., from shunting train wagons in shunting yards, shunting trams in depots, or in stacking cargo containers on cargo ships or storage yards in transshipment terminals. 
We consider the problem of sorting a permutation of n integers 1,2,...,n using k >= 2 stacks. In this problem, elements from the input sequence are pushed one-by-one (in the order of the elements in the sequence) to one of the k stacks. At any time, an element from a stack can be popped and pushed to another stack; such an operation is called a shuffle. Also, at any time, an element can be popped from a stack and placed to the output sequence. We can only place the elements to the output in the increasing order of their value such that at the end the output is the ordered sequence of the elements. The problem asks to minimize the number of shuffles in the process. 
It is known that for k >= 4, the problem is NP-hard, and that there is no approximation algorithm unless P=NP. For k >= 3, it is known that at most O(n log n) shuffles are needed for any input sequence. For the case when k=2, there exist input sequences that require Omega(n^{2-epsilon}) shuffles, for any epsilon>0. Nothing substantially more is known for the case of k=2. In this paper, we study the following variant of the problem with k=2 stacks: no shuffle and no placement to the output sequence can happen before every element is in one of the two stacks. We show that our problem can be seen as the MinUnCut problem by providing a polynomial-time reduction, and thus we show that there exists a randomized O(sqrt{log n})-approximation algorithm and a deterministic O(log n)-approximation algorithm for our problem.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Sorting
  • Stacks
  • Optimization
  • Algorithms
  • Reduction
  • MinUnCut

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. 𝒪(√log n) Approximation Algorithms for min UnCut, min 2CNF Deletion, and Directed Cut Problems. In Proc. Annual ACM Symposium on Theory of Computing (STOC), pages 573-581. ACM, 2005. Google Scholar
  2. Therese Biedl, Alexander Golynski, Angèle M. Hamel, Alejandro López-Ortiz, and J. Ian Munro. Sorting with networks of data structures. Discrete Applied Mathematics, 158(15):1579-1586, 2010. URL: https://doi.org/10.1016/j.dam.2010.06.007.
  3. Ulrich Blasum, Michael R Bussieck, Winfried Hochstättler, Christoph Moll, Hans-Helmut Scheel, and Thomas Winter. Scheduling Trams in the Morning. Mathematical Methods of Operations Research, 49(1):137-148, 1999. Google Scholar
  4. Miklós Bóna. A survey of stack-sorting disciplines. The Electronic Journal of Combinatorics, 9(2):A1.1-A1.16, 2003. URL: http://eudml.org/doc/123106.
  5. Héctor J Carlo, Iris FA Vis, and Kees Jan Roodbergen. Storage Yard Operations in Container Terminals: Literature Overview, Trends, and Research Directions. European journal of operational research, 235(2):412-430, 2014. Google Scholar
  6. S. Even and A. Itai. Queues, stacks, and graphs. In Proc. International Symposium on the Theory of Machines and Computations, pages 71-86. Academic Press, 1971. Google Scholar
  7. Stefan Felsner and Martin Pergel. The Complexity of Sorting With Networks of Stacks and Queues. In Proc. European Symposium on Algorithms (ESA), pages 417-429. Springer, 2008. Google Scholar
  8. Naveen Garg, Vijay V Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi) cut theorems and their applications. SIAM Journal on Computing, 25(2):235-251, 1996. Google Scholar
  9. Brady Gilg, Torsten Klug, Rosemarie Martienssen, Joseph Paat, Thomas Schlechte, Christof Schulz, Senan Seymen, and Alexander Tesch. Conflict-Free Railway Track Assignment at Depots. Journal of rail transport planning &management, 8(1):16-28, 2018. Google Scholar
  10. Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  11. Mohamed Hamdouni, Guy Desaulniers, Odile Marcotte, François Soumis, and Marianne Van Putten. Dispatching Buses in a Depot Using Block Patterns. Transportation Science, 40(3):364-377, 2006. Google Scholar
  12. Stephan A Hartmann and Thomas A Runkler. Online Optimization of a Color Sorting Assembly Buffer Using Ant Colony Optimization. In Operations Research Proceedings 2007, pages 415-420. Springer, 2008. Google Scholar
  13. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proc. Symposium on the Complexity of Computer Computations, pages 85-103. Springer, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  14. Donald Ervin Knuth. The Art of Computer Programming, volume 1, chapter 2.2.1, pages 238-243. Addison-Wesley, 2nd edition, 1987. Google Scholar
  15. Donald Ervin Knuth. The Art of Computer Programming, volume 3, chapter 5.2.3, page 168. Addison-Wesley, 2nd edition, 1998. Google Scholar
  16. Felix G König, Macro Lübbecke, Rolf Möhring, Guido Schäfer, and Ines Spenke. Solutions to Real-World Instances of PSPACE-Complete Stacking. In Proc. European Symposium on Algorithms (ESA), pages 729-740. Springer, 2007. Google Scholar
  17. Felix G König and Marco E Lübbecke. Sorting With Complete Networks of Stacks. In Proc. International Symposium on Algorithms and Computation (ISAAC), pages 895-906. Springer, 2008. Google Scholar
  18. Adeline Pierrot and Dominique Rossin. 2-Stack Sorting is Polynomial. Theory of Computing Systems, 60(3):552-579, 2017. URL: https://doi.org/10.1007/s00224-016-9743-8.
  19. Marc Pont. The Bi-Stack Sorting Problem. Master’s thesis, Department of Data Science and Knowledge Engineering, Maastricht University, 2019. Google Scholar
  20. Rebecca Smith. Comparing Algorithms for Sorting with t Stacks in Series. Annals of Combinatorics, 8(1):113-121, 2004. URL: https://doi.org/10.1007/s00026-004-0209-3.
  21. Robert Tarjan. Sorting Using Networks of Queues and Stacks. J. ACM, 19(2):341-346, 1972. Google Scholar
  22. Kevin Tierney, Dario Pacino, and Rune Møller Jensen. On the Complexity of Container Stowage Planning Problems. Discrete Applied Mathematics, 169:225-230, 2014. Google Scholar
  23. W. Unger. On the k-colouring of circle graphs. In Proc. International Symposium on Theoretical Aspects of Computer Science (STACS), pages 61-72. Springer, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact