Defining Equitable Geographic Districts in Road Networks via Stable Matching
Defining Equitable Geographic Districts in Road Networks via Stable Matching
复制标题
通过稳定匹配定义道路网络中的公平地理区域
DOI：
10.1145/3139958.3140015
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nil Mamano
中科院分区：
文献类型：
--
作者：
D. Eppstein;M. Goodrich;Doruk Korkmaz;Nil Mamano
我们介绍了一种新的方法来定义道路网络中的地理区域，使用稳定的匹配。在这种方法中，每个地理区域都是根据一个中心来定义的，该中心标识了感兴趣的位置，例如邮局或投票站，并且所有其他网络顶点都必须用它们所关联的中心来标记。我们专注于定义公平的地理区域，因为每个区域都有相同数量的顶点，并且分配在地理距离方面是稳定的。也就是说，不存在未分配的顶点中心对，使得两者将彼此偏好于其当前分配。我们解决这个问题，使用一个版本的经典的稳定匹配问题，称为对称稳定匹配，其中两组元素的偏好服从一定的对称性。我们表明，对于一个平面图或道路网络与n个节点和k个中心，该问题可以解决在O（n <$n log n）的时间，这提高了O（nk）的运行时间使用经典的Gale-Shapley稳定匹配算法时，k是大的。最后，我们提供的实验结果，这些算法和一个启发式算法，表现优于Gale-Shapley算法的任何范围内的K值的道路网络。
We introduce a novel method for defining geographic districts in road networks using stable matching. In this approach, each geographic district is defined in terms of a center, which identifies a location of interest, such as a post office or polling place, and all other network vertices must be labeled with the center to which they are associated. We focus on defining geographic districts that are equitable, in that every district has the same number of vertices and the assignment is stable in terms of geographic distance. That is, there is no unassigned vertex-center pair such that both would prefer each other over their current assignments. We solve this problem using a version of the classic stable matching problem, called symmetric stable matching, in which the preferences of the elements in both sets obey a certain symmetry. We show that, for a planar graph or road network with n nodes and k centers, the problem can be solved in O(n √ n log n) time, which improves upon the O(nk) runtime of using the classic Gale--Shapley stable matching algorithm when k is large. Finally, we provide experimental results on road networks for these algorithms and a heuristic algorithm that performs better than the Gale--Shapley algorithm for any range of values of k.