A mean identity for longest increasing subsequence problems
From MaRDI portal
Abstract: We show that a wide variety of generalized increasing subsequence problems admit a one parameter family of extensions for which we can exactly compute the mean length of the longest increasing subsequence. By the nature of the extension, this gives upper bounds on the mean in the unextended model, which turn out to be asymptotically tight for all of the models that have so far been analyzed. A heuristic analysis based on this fact gives not just the asymptotic mean but also the asymptotic scale factor, again agreeing with all known cases.
This page was built for publication: A mean identity for longest increasing subsequence problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6470363)
