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.001MaRDI QIDQ310679zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• The expected length of a shortest path
• On Shortest Paths in Graphs with Random Weights
• Shortest paths with a cost constraint: a probabilistic analysis
• scientific article; zbMATH DE number 1416161
• Bounding variance and expectation of longest path lengths in dags

Cites work

• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• A note on shortest path, assignment, and transportation problems
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• On linear programs with random costs
• Random assignment 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q310679)