Spring 2017: Theory Seminar
Bren Hall, Room 1423, 1:00pm

May 19, 2017:

Stable graph matching and the post office problem in road networks

Nil Mamano

Abstract: We study a graph-based version of the classic stable matching problem, in which nodes are stably matched to a subset of nodes denoted centers, as prioritized by their shortest-path distances, so that each center is apportioned a certain number of nodes. We show that for a planar graphs n nodes and $k$ centers, the problem can be solved in $O(n^{1.5} \log n)$ time, which improves over the $O(kn)$ running time of the Gale-Shapley algorithm when $k$ is large. In order to do this, we use a novel dynamic nearest-neighbor data structure based on shortest-path distances. This data structure, which might be of independent interest for other applications, maintains a subset of nodes of the graph and allows nearest-neighbor queries (for other nodes in the graph) in $O(n^{0.5})$ time and updates in $O(n^{0.5} \log n)$ time.

Joint work with David Eppstein, Michael T. Goodrich, and Doruk Korkmaz