Faster Algorithms for Stable Allocation Problems

作者：Dean Brian C^*; Munshi Siddharth

来源：Algorithmica, 2010, 58(1): 59-81.

DOI：10.1007/s00453-010-9416-y

• Stable allocation
• Stable marriage
• Sable matching

We consider a high-multiplicity generalization of the classical stable matching problem known as the stable allocation problem, introduced by Ba < ou and Balinski in 2002. By leveraging new structural properties and sophisticated data structures, we show how to solve this problem in O(mlog n) time on a bipartite instance with n vertices and m edges, improving the best known running time of O(mn). Building on this algorithm, we provide an algorithm for the non-bipartite stable allocation problem running in O(mlog n) time with high probability. Finally, we give a polynomial-time algorithm for solving the "optimal" variant of the bipartite stable allocation problem, as well as a 2-approximation algorithm for the NP-hard "optimal" variant of the non-bipartite stable allocation problem.

• 出版日期2010-9