We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 05 June 2012
Given a weighted undirected graph, the maximum matching problem is to find a matching with maximum total weight. In his seminal paper, Edmonds [35] described an integral polytope for the matching problem, and the famous Blossom Algorithm for solving the problem in polynomial time.
In this chapter, we will show the integrality of the formulation given by Edmonds [35] using the iterative method. The argument will involve applying uncrossing in an involved manner and hence we provide a detailed proof. Then, using the local ratio method, we will show how to extend the iterative method to obtain approximation algorithms for the hypergraph matching problem, a generalization of the matching problem to hypergraphs.
Graph matching
Matchings in bipartite graphs are considerably simpler than matchings in general graphs; indeed, the linear programming relaxation considered in Chapter 3 for the bipartite matching problem is not integral when applied to general graphs. See Figure 9.1 for a simple example.
Linear programming relaxation
Given an undirected graph G = (V, E) with a weight function w: E → ℛ on the edges, the linear programming relaxation for the maximum matching problem due to Edmonds is given by the following LPM(G). Recall that E(S) denotes the set of edges with both endpoints in S ⊆ V and x(F) is a shorthand for ∑e∈Fxe for F ⊆ E.
Although there are exponentially many inequalities in LPM(G), there is an efficient separation oracle for this linear program, obtained by Padberg and Rao using Gomory-Hu trees.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
