A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in Directed Acyclic Graphs and reliability

Stéphane Chrétien (1) , Franck Corset (2)

1 NPL - National Physical Laboratory [Teddington]
2 FIGAL - Fiabilité et Géométrie Aléatoire

The paper studies the expectation of the inspection time in complex aging systems , i.e. the length of the shortest path in a Directed Acyclic Graph, with random costs on egdes. We give a lower bound for this expectation.

Mots clés: Dyer-Frieze-McDiarmid's inequality; Shortest path; Random networks; Random linear programming; Reliability; Maintenance

Domaines: Statistiques [math.ST]

Stéphane Chrétien, Franck Corset. A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in Directed Acyclic Graphs and reliability. Statistics and Probability Letters, 2016, 117, pp.221-230. ⟨10.1016/j.spl.2016.06.001⟩. ⟨hal-01344047⟩