A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability

DOI10.1016/j.spl.2016.06.001zbMath1387.90075OpenAlexW2423820463MaRDI QIDQ310679

Stéphane Chrétien, Franck Corset

Publication date: 8 September 2016

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.spl.2016.06.001

zbMATH Keywords

reliabilityshortest pathmaintenancerandom networksDyer-Frieze-McDiarmid's inequalityrandom linear programming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Linear programming (90C05) Reliability, availability, maintenance, inspection in operations research (90B25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• Random assignment problems
• On linear programs with random costs
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• A note on shortest path, assignment, and transportation problems

This page was built for publication: A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability