Computing at Glasgow University
Paper ID: 9324
DCS Tech Report Number: TR-2010-312

Integral Stable Allocation Problem on Graphs
Biro,P. Fleiner,T.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 2010

As a generalisation of the stable matching problem Baiou and Balinski defined the stable allocation problem for bipartite graphs, where both the edges and the vertices may have capacities. They constructed a so-called inductive algorithm, that always finds a stable allocation in strongly polynomial time. Here, we generalise their algorithm for non-bipartite graphs with integral capacities. We show that the algorithm does not remain polynomial, although we also present a scaling technique that makes the algorithm weakly polynomial.

Keywords: stable matching problem, roommates problem, stable allocation problem

PDF Bibtex entry Endnote XML