I'm interested in the possibility of fast algorithms for the following two problems on permutations.
1)
Given a permutation $\pi$ and an integer $k$, compute a pair $(\mathcal{C},\mathcal{A})$ where $\mathcal{C}$ is a maximum $k$-chain and $\mathcal{A}$ is a corresponding $l$-antichain certifying the optimality of $\mathcal{C}$.
If you only care about $\mathcal{C}$, this can be done in $O(k n \log n)$ by an involved algorithm ('Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms' by S. Felsner and L. Wernisch). It seems possible to obtain a simpler algorithm that would also provide a certificate.
2)
Given a permutation $\pi$, compute the pair of Young tableaux $(P,Q)$ associated to $\pi$ by the Robinson-Schensted bijection. Is it possible to do it in subquadratic time?
Note: if we only care about the first $k$ rows of each tableau this can be done in $O(k n \log n)$ time in the RAM model; by Greene theorem, the cumulated size of the first $k$ rows gives the cost of an optimum solution for 1), without providing an explicit solution. Thus question 1) seems to require a different approach.
