Timeline for A simplified/harder 2-sequence longest common sub-sequence (LCS) problem
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 3, 2012 at 10:33 | vote | accept | javy1985114 | ||
| Sep 3, 2012 at 10:33 | vote | accept | javy1985114 | ||
| Sep 3, 2012 at 10:33 | |||||
| Sep 3, 2012 at 5:46 | comment | added | Philippe Nadeau | The method is a theorem: the best possible value for the sum length of k disjoint increasing subsequences is exactly the sum of the first k parts of the shape given by the Schensted correspondence. This is in C. Greene, "An extension of Schensted's theorem", Adv. in Math. 1974. I checked this article, and in fact Greene also indicates how to find an optimal set of sequences achieving this value if that's what you're interested in. | |
| Sep 3, 2012 at 3:42 | comment | added | javy1985114 | Hi, Philippe Nadeau, thanks so much for your comments! It benefit me a lot! I tried some simple examples just now, and the results show that the method is optimal for k=2. say the sum of first k parts as you said. Do you think the method is also optimal for any value of k? The method seems to be so greedy, so I am afraid it becomes sub-optimal when k gets larger. Thanks so much! | |
| Sep 1, 2012 at 15:36 | history | answered | Philippe Nadeau | CC BY-SA 3.0 |