60 citations · 366 across the 26 of their papers we have counts for
7 papers · 1 filter
How many longest increasing subsequences are there?
Phil Krabbe, Hendrik Schawe, Alexander K. Hartmann
We study the entropy of longest increasing subsequences (LIS), i.e., the logarithm of the number of distinct LIS. We consider two ensembles of sequences, namely random permutat…
Large deviations of the length of the longest increasing subsequence of random permutations and random walks
Jörn Börjes, Hendrik Schawe, Alexander K. Hartmann
We study numerically the distributions of the length of the longest increasing subsequence (LIS) for the two cases of random permutations and of one-dimensional random walks. U…
Large-deviation properties of the largest biconnected component for random graphs
Hendrik Schawe, Alexander K. Hartmann
We study the size of the largest biconnected components in sparse Erdős-Rényi graphs with finite connectivity and Barabási-Albert graphs with non-integer mean degree. Using a stati…
Ground state energy of noninteracting fermions with a random energy spectrum
Hendrik Schawe, Alexander K. Hartmann, Satya N. Majumdar +1
We derive analytically the full distribution of the ground-state energy of non-interacting fermions in a disordered environment, modelled by a Hamiltonian whose spectrum consis…
Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
Hendrik Schawe, Jitesh Kumar Jha, Alexander K. Hartmann
We study the energy landscape of the Traveling Salesperson problem (TSP) using exact ground states and a novel linear programming approach to generate excited states with closely d…
Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
Hendrik Schawe, Roman Bleim, Alexander K. Hartmann
Here we study the NP-complete -SAT problem. Although the worst-case complexity of NP-complete problems is conjectured to be exponential, there exist parametrized random ensemble…
Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
Hendrik Schawe, Alexander K. Hartmann
The Traveling Salesperson problem asks for the shortest cyclic tour visiting a set of cities given their pairwise distances and belongs to the NP-hard complexity class, which means…