RSK Algorithm with Applications to Random Combinatorial Optimizations
报告题目(Title)：RSK Algorithm with Applications to Random Combinatorial Optimizations
报告人(Speaker)： 苏中根 教授 （浙江大学）
地点(Place)：后主楼 1223
时间(Time)：2020-12-17（周四）， 16:00-17:30
邀请人(Inviter)：何辉
报告摘要
The Robinson-Schensted-Knuth algorithm was invented to find the length of the longest increasing subsequences from a finite sequence of distinct real numbers. It is arguably recognized as one of the most useful algorithms in the field of combinatorial optimization. In this talk we will first describe such an algorithm, and then focus on its applications to random combinatorial optimization problems. In particular, we briefly review two remarkable results: Baik, Defit and Johansson (JAMS 1999) discovered the limiting distribution of the length of longest increasing subsequences of a sequence of i.i.d. uniform random variables; Johnsson (CMP 2000) established the limiting distribution of last passage percolation with i.i.d. geometric weights in the planar lattice. It turns out that a new era for the study of random growth processes has been since then open to us.
