New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches.
Ulrich MeyerAndrei NegoescuVolker WeichertPublished in: TAPAS (2011)
Keyphrases
- average case
- worst case
- shortest path
- single source
- shortest path problem
- worst case analysis
- shortest path algorithm
- uniform distribution
- upper bound
- computational complexity
- machine learning algorithms
- combinatorial optimization problems
- sample complexity
- approximation algorithms
- random walk
- active learning
- learning algorithm
- average case complexity