Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.
Patrick BriestParinya ChalermsookSanjeev KhannaBundit LaekhanukitDanupon NanongkaiPublished in: WINE (2010)
Keyphrases
- shortest path
- shortest path problem
- shortest path algorithm
- road network
- optimal path
- routing algorithm
- geodesic distance
- shortest distance
- finding the shortest path
- computational complexity
- dijkstra algorithm
- weighted graph
- path length
- minimal surface
- travel time
- approximation algorithms
- steiner tree
- flow graph
- source node
- np hard
- path selection
- dynamic environments
- minimum cost flow
- random walk
- np complete