Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation Schemes

DOI10.1109/TC.2011.61zbMath1365.68269OpenAlexW2140647291MaRDI QIDQ5277615

Krishnaiyan Thulasiraman, Guoliang Xue, Dejun Yang, Y. Xiao, Xi Fang

Publication date: 12 July 2017

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tc.2011.61

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

A fully polynomial time approximation scheme for the probability maximizing shortest path problem, Finding cheapest deadline paths, Itinerary planning with time budget for risk-averse travelers, An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges