Berlin 2018 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 66: Poster: Stat. Phys. (Gen., Critical Phen., Biol.)
DY 66.2: Poster
Thursday, March 15, 2018, 15:30–18:00, Poster A
The longest increasing subsequence of a sequence problem: A large deviation study — •Jörn Börjes, Hendrik Schawe, and Alexander K. Hartmann — Institut für Physik, Carl von Ossietzky Universität Oldenburg
The longest increasing subsequence (LIS) problem asks for the longest subsequence in which the elements are in sorted order, lowest to highest and part of the given sequence with length n. The elements indices of the sequence do not need to be continuous to become a LIS. There is an exact mapping between a specific polynuclear growth model and the so called LIS problem [1]. This problem is numerically solved by an algorithm with complexity O(n logn). We study the distribution of the length of the LIS up to the large deviations. We compare our numerical results to the analytically known results. Using specific large-deviation approaches [2], probability distributions can be sampled over a large range of the support, down to probabilities like 10−40.
[1] Satya N. Majumdar and Sergei Nechaev, Phys. Rev. E 69
[2] A.K. Hartmann Phys. Rev. E 65, OSG 202 (2002)