Abstrakt. Vi anser att problemet med att hitta kortaste vägar i en graf med oberoende slumpmässigt fördelade kantlängder. Vårt mål är att maximera sannolikheten för att banans längd inte överstiger ett givet tröskelvärde (deadline). Vi ger en överraskande exakt n  på (log n) algoritm för fallet med normalt fördelade kantlängder, som är baserad på kvasi-konvex maximering. Vi bevisar sedan genomsnittliga och utjämnade polynom gränser för denna algoritm, som också översätter till genomsnittliga och utjämnade gränser för den parametriska kortaste vägen problem, och sträcker sig till en mer allmän icke-konvex optimering inställning. Vi överväger också ett antal andra kant längdfördelningar, vilket ger en rad exakta och approximativa system.
Nikolova m.fl. REF studerade problemet med att maximera sannolikheten för att längden på den valda banan är mindre än någon given parameter.
Stochastic Shortest Paths Via Quasi-convex Maximization
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}