Data Procurement for Shortest Paths on Random Graphs

While Dijkstra's algorithm finds the shortest path between two nodes on a graph with known edge weights, we approach the shortest paths problem for graphs with random edge weights described by known probability distributions. We introduce the idea of a budget of size k which allows us to replace k random edges with numbers drawn from the edges' distributions. Our problem is to determine which edges to replace with random realizations to minimize the minimum expected path distance across all paths between two nodes, given the realized edge weights. We evaluate several greedy heuristics, with different lookaheads, for choosing edges. We also prove that any greedy heuristic with lookahead less than the budget has no finite approximation ratio to the optimal policy.

Name thesis:degree_name

AB

Level thesis:degree_level

Undergraduate

Grantor

Harvard College

Year dc:date.issued

2016

Author dc:creator

• Su, Adam Hao

Language dc:language.iso

en

Repository record dc:identifier.uri

http://nrs.harvard.edu/urn-3:HUL.InstRepos:38811464

OAI identifier oai:identifier

oai:dash.harvard.edu:1/38811464