A Lower Bound for the Shortest Path Problem.
Ketan MulmuleyPradyut ShahPublished in: Computational Complexity Conference (2000)
Keyphrases
- shortest path problem
- lower bound
- upper bound
- shortest path
- single source
- interval data
- branch and bound algorithm
- combinatorial optimization problems
- branch and bound
- lower and upper bounds
- np hard
- multiple objectives
- objective function
- optimal solution
- bi objective
- directed graph
- directed acyclic graph
- lower bounding
- sufficiently accurate
- worst case
- polynomial approximation
- optimization problems
- linear programming relaxation
- greedy algorithm
- data sources
- competitive ratio
- cost function