Bipartite Weighted Matching
What is a Weighted Matching in a Bipartite Graph?
A matching in a graph G=(V,E) is a subset M of the edges E such that
no two edges in M share a common end node. If the edges of the graph have
an associated weight, then a maximum weighted matching is a matching
such that the sum of the weights of the edges in the matching is maximum.
A graph is bipartite if it has two kinds of nodes and the edges
are only allowed between nodes of different kind. A matching in a bipartite
graph therefore assigns nodes of one kind to nodes of the other kind.
Matchings in bipartite graphs can be computed more efficiently than matchings
in general (=non-bipartite) graphs.
Intuition: Suppose we have a set of workers and a set of machines.
These are the two kinds of nodes in our bipartite graph. We know which
worker can handle which machines. This defines the edges of the bipartite
graph. Additionally, we know the profit of assigning worker w
to machine m. This defines the edge weight. Our task in the
maximum weighted matching problem is to assign workers to machines in
such a way that the total profit is maximum.
Proof of Optimality of the Resulting Matching
All functions for computing weighted matchings in bipartite graphs provide
a proof of optimality in the form of a potential function pot
for the nodes of the graph. The potential function corresponds to the
node cover in Maximum Cardinality
Matching in Bipartite Graphs. Details can be found in the LEDA
Book.
The Number Type for the Edge Weights
All functions in this section are template functions. The template parameter
NT can be instantiated with any number
type. Additionally, there are preinstantiated versions for int
and double. The names of the template functions have suffix
_T and the functions without suffix _T are the
preinstantiated versions
The reason why we did not restrict our algorithms to int
and double is that the number types int, float,
and double provided by C++ are only crude approximations
of the mathematical counterparts: ints can overflow, the
arithmetic for floats and doubles incurs rounding
errors. The functions in this section only perform correctly if all arithmetic
is performed without rounding errors.
LEDA Functions for Bipartite Weighted Matching
MAX_WEIGHT_BIPARTITE_MATCHING_T() computes a maximum
weighted matching in a bipartite graph. MAX_WEIGHT_BIPARTITE_MATCHING_T()
is a template function. The template parameter NT can be
instantiated with any number type.
CHECK_MWB_T() checks if the result of MAX_WEIGHT_BIPARTITE_MATCHING_T(),
a list<edge>
M and a node_array<NT>
pot, are a maximum weighted matching and a corresponding potential
function of the bipartite graph G.
Example
of MAX_WEIGHT_BIPARTITE_MATCHING_T() and CHECK_MWBM_T()
MAX_WEIGHT_BIPARTITE_MATCHING() is the name of the
preinstantiated versions of MAX_WEIGHT_BIPARTITE_MATCHING_T().
There is one function for edge weights of type int and one
for double.
CHECK_MWB() checks if the result of MAX_WEIGHT_BIPARTITE_MATCHING(),
a list<edge> M
and a node_array<int>
pot , respectively node_array<double>
pot, are a maximum weighted matching and a corresponding potential
function of the bipartite graph G.
Important Notice: MAX_WEIGHT_BIPARTITE_MATCHING()
only performs correctly if all arithmetic is performed without rounding
errors and without overflows. If you are not sure about this, you should
use MAX_WEIGHT_BIPARTITE_MATCHING_T() with one of the LEDA
number types. MAX_WEIGHT_BIPARTITE_MATCHING() for int
issues a warning if incorrect results are possible. MAX_WEIGHT_BIPARTITE_MATCHING()
for double computes a maximum weighted matching for modified
edge weights in order to avoid internal arithmetic problems. Details can
be found in the LEDA Book. Using
the following function you can do the weight modification explicitely.
MWBM_SCALE_WEIGHTS() modifies the edge weights for
MAX_WEIGHT_BIPARTITE_MATCHING() with double
in order to avoid internal arithmetic problems. The function returns false
if it changed some edge capacities and true otherwise.
Example
of MAX_WEIGHT_BIPARTITE_MATCHING(),CHECK_MWBM(),MWBM_SCALE_WEIGHTS()
Running times
For a bipartite graph G=(V,E), the running times of of computing
a maximum weighted matching is O(|V|*(|E|+|V|log|V|)). The checking and
scaling functions are linear in the size of the graph.
Tips
- Use
MAX_WEIGHT_BIPARTITE_MATCHING_T() to compute a maximum
weighted matching in a bipartite graph.
- If you are determined to use
MAX_WEIGHT_BIPARTITE_MATCHING()be
aware of the arithmetic problems that may arise. In case of double
edge weights use MWBM_SCALE_WEIGHTS() to modify the edge
weights explicitely.
- Use
CHECK_MWBM_T() and CHECK_MWBM() to ensure
the correctness of your result. Checking the result is much easier than
computing a maximum weighted matching in a bipartite graph. Therefore,
CHECK_MWBM_T() and CHECK_MWBM() are less complicated
and less error prone. Moreover, checking is only linear in the size
of the graph. So, the overhead is quite small.
|