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.001zbMATH Open1387.90075OpenAlexW2423820463MaRDI QIDQ310679FDOQ310679

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

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)