Affordable Access

The integral stable allocation problem on graphs

Authors
Publisher
Elsevier
Publication Date
Disciplines
  • Computer Science

Abstract

As a generalisation of the stable matching problem Baton and Balinski (2002) 111 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.

There are no comments yet on this publication. Be the first to share your thoughts.