DPG Phi
Verhandlungen
Verhandlungen
DPG

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)

100% | Mobile Layout | Deutsche Version | Contact/Imprint/Privacy
DPG-Physik > DPG-Verhandlungen > 2018 > Berlin