Processing math: 100%

ICS Theory Group

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(n1.5logn) 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(n0.5) time and updates in O(n0.5logn) time.

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