Faster algorithms for stable allocation problems

Faster algorithms for stable allocation problems

0.00 Avg rating0 Votes
Article ID: iaor20104960
Volume: 58
Issue: 1
Start Page Number: 59
End Page Number: 81
Publication Date: Sep 2010
Journal: Algorithmica
Authors: ,
Keywords: matching
Abstract:

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(mlogn) 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(mlogn) 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.

Reviews

Required fields are marked *. Your email address will not be published.