On the Stable Marriage of MaximumWeight Royal Couples

Contents

In this paper we provide a comparison, both analytic and empirical, of two algorithms that were used in the literature for ensuring a 1:1 cardinality constraint in schema matching. We compare an application of a solution to the maximum weighted bipartite graph to schema matching to that of solving a stable marriage problem. Using real-world testbed we show that in practice, both algorithms yield similar results. We then analyze the roots of this similarity, by offering a variation of the stable marriage algorithm for schema matching (royal couples) and show the relationships between the royal couples stable marriage problem and the maximum weights bipartite graph problem. Finally, we propose a new heuristic for schema matching, based on the royal couples observation and show its performance with respect to the two algorithms.