Document Open Access Logo

Fast RSK Correspondence by Doubling Search

Author Alexander Tiskin

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.86.pdf
  • Filesize: 0.69 MB
  • 10 pages

Document Identifiers

Author Details

Alexander Tiskin
  • Department of Mathematics and Computer Science, St. Petersburg State University, Russia

Funding

This work was supported by the Russian Science Foundation under grant no. 22-21-00669, https://www.rscf.ru/en/project/22-21-00669/.

Acknowledgements

I thank Nikolay Vasilyev, Vasilii Duzhin and Artem Kuzmin for advice and fruitful discussions.

Cite As Get BibTex

Alexander Tiskin. Fast RSK Correspondence by Doubling Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 86:1-86:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.86

Abstract

The Robinson-Schensted-Knuth (RSK) correspondence is a fundamental concept in combinatorics and representation theory. It is defined as a certain bijection between permutations and pairs of Young tableaux of a given order. We consider the RSK correspondence as an algorithmic problem, along with the closely related k-chain problem. We give a simple, direct description of the symmetric RSK algorithm, which is implied by the k-chain algorithms of Viennot and of Felsner and Wernisch. We also show how the doubling search of Bentley and Yao can be used as a subroutine by the symmetric RSK algorithm, replacing the default binary search. Surprisingly, such a straightforward replacement improves the asymptotic worst-case running time for the RSK correspondence that has been best known since 1998. A similar improvement also holds for the average running time of RSK on uniformly random permutations.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
Keywords
  • combinatorics of permutations
  • Robinson-Schensted-Knuth correspondence
  • k-chains
  • RSK algorithm

Metrics

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

References

  1. Jon Louis Bentley and Andrew Chi-Chih Yao. An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3):82-87, 1976. URL: https://doi.org/10.1016/0020-0190(76)90071-5.
  2. Sergei Bespamyatnikh and Michael Segal. Enumerating longest increasing subsequences and patience sorting. Information Processing Letters, 76:7-11, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00124-1.
  3. Henrik Blunck and Jan Vahrenhold. In-Place Algorithms for Computing (Layers of) Maxima. Algorithmica, 57:1-21, 2010. URL: https://doi.org/10.1007/s00453-008-9193-z.
  4. Adam L. Buchsbaum and Michael T. Goodrich. Three-Dimensional Layers of Maxima. Algorithmica, 39:275-286, 2004. URL: https://doi.org/10.1007/s00453-004-1082-5.
  5. Jeff Calder, Selim Esedoḡlu, and Alfred O. Hero. A PDE-based Approach to Nondominated Sorting. SIAM Journal on Numerical Analysis, 53:82-104, 2015. URL: https://doi.org/10.1137/130940657.
  6. E W Dijkstra. Some beautiful arguments using mathematical induction. Acta Informatica, 13(1):1-8, 1980. URL: https://doi.org/10.1007/BF00288531.
  7. V. S. Duzhin and N. N. Vasilyev. Asymptotic behavior of normalized dimensions of standard and strict Young diagrams: growth and oscillations. Journal of Knot Theory and Its Ramifications, 25(12):1642002, 2016. URL: https://doi.org/10.1142/S0218216516420025.
  8. P Erdös and G Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  9. Stefan Felsner and Lorenz Wernisch. Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms. SIAM Journal on Computing, 28:192-209, 1998. URL: https://doi.org/10.1137/S0097539794266171.
  10. Michael L Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11:29-35, 1975. URL: https://doi.org/10.1016/0012-365X(75)90103-X.
  11. Curtis Greene. An Extension of Schensted’s Theorem. Advances in Mathematics, 14:254-265, 1974. Google Scholar
  12. Dan Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997. URL: https://doi.org/10.1017/CBO9780511574931.
  13. D E Knuth. Permutations, matrices, and generalized Young tableaux. Pacific Journal of Mathematics, 34(3):709-727, 1970. Google Scholar
  14. S. N. Majumdar and S. Nechaev. Exact asymptotic results for the Bernoulli matching model of sequence alignment. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 72(2):020901, 2005. URL: https://doi.org/10.1103/PhysRevE.72.020901.
  15. G de B Robinson. On the representations of the symmetric group. American Journal of Mathematics, 60:745-760, 1938. URL: https://doi.org/10.2307/2372326.
  16. D. Romik. The Number of Steps in the Robinson-Schensted Algorithm. Functional Analysis and Its Applications, 39(2):152-155, 2005. URL: https://doi.org/10.1007/s10688-005-0030-8.
  17. Dan Romik. The Surprising Mathematics of Longest Increasing Subsequences. Cambridge University Press, Cambridge, 2014. URL: https://doi.org/10.1017/CBO9781139872003.
  18. C. Schensted. Longest Increasing and Decreasing Subsequences. Canadian Journal of Mathematics, 13:179-191, 1961. URL: https://doi.org/10.4153/CJM-1961-015-3.
  19. M. P. Schützenberger. Quelques remarques sur une construction de Schensted. Mathematica Scandinavica, 12:117-128, 1963. URL: https://doi.org/10.7146/math.scand.a-10676.
  20. Richard P. Stanley. Algebraic Combinatorics. Undergraduate Texts in Mathematics. Springer, New York, NY, 2013. URL: https://doi.org/10.1007/978-1-4614-6998-8.
  21. Hugh Thomas and Alexander Yong. Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm. Advances in Applied Mathematics, 46(1-4):610-642, 2011. URL: https://doi.org/10.1016/j.aam.2009.07.005.
  22. N. N. Vasiliev and V. S. Duzhin. A Study of the Growth of the Maximum and Typical Normalized Dimensions of Strict Young Diagrams. Journal of Mathematical Sciences, 216(1):53-64, 2016. URL: https://doi.org/10.1007/s10958-016-2887-x.
  23. G. Viennot. Une forme geometrique de la correspondance de Robinson-Schensted. In Combinatoire et Représentation du Groupe Symétrique, volume 579 of Lecture Notes in Mathematics, pages 29-58. Springer, 1977. URL: https://doi.org/10.1007/BFb0090011.
  24. G. Viennot. Chain and antichain families, grids and Young tableaux. Annals of Discrete Mathematics, 23:409-463, 1984. URL: https://doi.org/10.1016/S0304-0208(08)73835-0.
  25. X Viennot. Growth diagrams and edge local rules. In Proceedings of GASCom, 2018. 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