English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The distribution of the computational cost of linear-programming (LP)relaxation for vertex cover problems on Erdos-Renyi random graphs is evaluatedby using the rare-event sampling method. As a large-deviation property,differences of the distribution for "easy" and "hard" problems are foundreflecting the hardness of approximation by LP relaxation. In particular, byevaluating the total variation distance between conditional distributions withrespect to the hardness, it is suggested that those distributions are almostindistinguishable in the replica symmetric (RS) phase while they asymptoticallydiffer in the replica symmetry breaking (RSB) phase. In addition, we seek for arelation to graph structure by investigating a similarity to bipartite graphs,which exhibits a quantitative difference between the RS and RSB phase. Theseresults indicate the nontrivial relation of the typical computational cost ofLP relaxation to the RS-RSB phase transition as present in the spin-glasstheory of models on the corresponding random graph structure.

Large-deviation Properties of Linear-programming Computational Hardness of the Vertex Cover Problem