Article ID Journal Published Year Pages File Type
6876246 Theoretical Computer Science 2014 8 Pages PDF
Abstract
An implicit linear description of the stable matching polytope is provided in terms of the blocker and antiblocker sets of constraints of the matroid-kernel polytope. The explicit identification of both these sets is based on a partition of the stable pairs in which each agent participates. Here, we expose the relation of such a partition to rotations. We provide a time-optimal algorithm for obtaining such a partition and establish some new related results; most importantly, that this partition is unique.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,