On dual integrality in matching problems

On dual integrality in matching problems

0.00 Avg rating0 Votes
Article ID: iaor19891038
Country: Netherlands
Volume: 8
Issue: 5
Start Page Number: 245
End Page Number: 249
Publication Date: Oct 1989
Journal: Operations Research Letters
Authors: ,
Abstract:

Edmonds and Johnson proved an integrality property of optimal dual solutions of matching problems, under the assumption that all the edge-costs are even integers. It is shown that the same conclusion holds if the costs are integers whose sum around any cycle is even. This result is a consequence of a form of the matching algorithm.

Reviews

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