{"id":{"repo_id":"harvard","oai_identifier":"oai:dash.harvard.edu:1/38811464"},"canonical_url":"https://search.dev.ndltd.org/etd/harvard/oai:dash.harvard.edu:1/38811464","repository":{"repo_id":"harvard","name":"Harvard University","base_url":"https://dash.harvard.edu/server/oai/request"},"display":{"title":"Data Procurement for Shortest Paths on Random Graphs","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Su, Adam Hao"],"institution":"Harvard College","degree_name":"AB","degree_level":"Undergraduate","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-06-21","date_published":"2016-06-21","updated_at":"2026-07-27T19:55:49Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://nrs.harvard.edu/urn-3:HUL.InstRepos:38811464","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Su, Adam Hao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-03-26T10:41:39Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-03-26T10:41:39Z"]},{"key":"dc:date.issued","label":"Date","values":["2016-06-21"]},{"key":"dc:type","label":"Dc Type","values":["Thesis or Dissertation"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Undergraduate"]},{"key":"thesis:degree_name","label":"Degree Name","values":["AB"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Harvard College"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://nrs.harvard.edu/urn-3:HUL.InstRepos:38811464"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Data Procurement for Shortest Paths on Random Graphs"]}]}],"canonical_facts":{"dc:creator":["Su, Adam Hao"],"dc:date.accessioned":["2019-03-26T10:41:39Z"],"dc:date.available":["2019-03-26T10:41:39Z"],"dc:date.issued":["2016-06-21"],"dc:description.abstract":["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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://nrs.harvard.edu/urn-3:HUL.InstRepos:38811464"],"dc:language.iso":["en"],"dc:title":["Data Procurement for Shortest Paths on Random Graphs"],"dc:type":["Thesis or Dissertation"],"thesis:degree_level":["Undergraduate"],"thesis:degree_name":["AB"],"thesis:institution_name":["Harvard College"]},"updated_at":"2026-07-27T19:55:49Z"}