I'm interested in the possibility of fast algorithms for the following two problems on permutations.


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.


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.

  • 2
    $\begingroup$ While you didn't introduce any definition to any of your assumptions, which are not common and not clear, and while the authors of that paper are claiming that their work is based on easy extension of another paper but you wrote it's really involved (I read the first three pages of paper, by my understanding their general idea is very natural, so I cannot see how it's so complicated if someone has enough base), by lack of all of these, I'll upvote this question because introduced an interesting topic to me. But I think if you provide questions with more details to be self contained is better. $\endgroup$ – Saeed Apr 25 '14 at 16:19
  • $\begingroup$ I don't like your patronizing tone, but still I'll try addressing your comments when possible. Also, thanks for the upvoting. $\endgroup$ – NisaiVloot Apr 25 '14 at 17:55
  • 2
    $\begingroup$ Actually I think you have many different accounts in the site like Grid_y_Bill, Super8, ... (Also I'm not sure if all of them are belong to one user or to the group of users). By the way I just try to probably help you to write your questions in more reasonable way. I found many of questions of this group of users as not a real question. But while it's not a real question, they bring some information about other fields which are not very popular among computer scientists. So even if you want introduce us to that concepts, it's better to be very clear in all of your definitions. $\endgroup$ – Saeed Apr 25 '14 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.