A maximum b-matching problem arising from median location models with applications to the roommates problem

A maximum b-matching problem arising from median location models with applications to the roommates problem

0.00 Avg rating0 Votes
Article ID: iaor19991101
Country: Netherlands
Volume: 80
Issue: 2
Start Page Number: 171
End Page Number: 194
Publication Date: Jan 1998
Journal: Mathematical Programming
Authors: ,
Keywords: game theory
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.

Reviews

Required fields are marked *. Your email address will not be published.