A Maximum b-Matching Problem Arising from Median Location Models with Applications to the Roommates Problem

Title:

Author:

Arie Tamir

Coauthor(s):

Joseph S.B. Mitchell

Session: WE2-I-CM200

Keywords: b-matchings, median location problems, roommates problem

Abstract:

We consider maximum b-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then the b-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case the b-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractional b-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model.