Bipartite Weighted Assignment
What is an Assignment in a Bipartite Graph?
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.
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. An assignment in
a bipartite graph is a matching M such that each node of the graph has
an incident edge in M. If the edges of the graph have an associated weight,
then a maximum (minimum) weighted assignment is an assignment
such that the sum of the weights of the edges is maximum (minimum).
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 assignment problem is to assign exactly one worker to
each machine 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 Assignment
Remark: In the following we describe only the functions for maximum
weighted assignment. The functions for minimum weighted assignment can
be used in exactly the same way. You only have to replace MAX by MIN in
the function names.
MAX_WEIGHT_ASSIGNMENT_T() computes a maximum weighted
assignment in a bipartite graph if one exists. MAX_WEIGHT_ASSIGNMENT_T()
is a template function. The template parameter NT can be
instantiated with any number type.
CHECK_MAX_WEIGHT_ASSIGNMENT_T() checks if the result
of MAX_WEIGHT_ASSIGNMENT_T(), a list<edge>
M and a node_array<NT>
pot, are a maximum weighted assignment and a corresponding potential
function of the bipartite graph G.
Example
of MAX_WEIGHT_ASSIGNMENT_T() and CHECK_MAX_WEIGHT_ASSIGNMENT_T()
MAX_WEIGHT_ASSIGNMENT() is the name of the preinstantiated
versions of MAX_WEIGHT_ASSIGNMENT_T(). There is one function
for edge weights of type int and one for double.
CHECK_MAX_WEIGHT_ASSIGNMENT() checks if the result
of MAX_WEIGHT_ASSIGNMENT(), a list<edge>
M and a node_array<int>
pot , respectively node_array<double>
pot, are a maximum weighted assignment and a corresponding potential
function of the bipartite graph G.
Important Notice: MAX_WEIGHT_ASSIGNMENT() 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_ASSIGNMENT_T()
with one of the LEDA number types. MAX_WEIGHT_ASSIGNMENT()
for int issues a warning if incorrect results are possible.
MAX_WEIGHT_ASSIGNMENT() for double computes
a maximum weighted assignment 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.
MWA_SCALE_WEIGHTS() modifies the edge weights for
MAX_WEIGHT_ASSIGNMENT() 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_ASSIGNMENT(),CHECK_MAX_WEIGHT_ASSIGNMENT(),MWA_SCALE_WEIGHTS()
Running times
For a bipartite graph G=(V,E), the running times of of computing
a maximum (minimum) weighted assignment is O(|V|*(|E|+|V|log|V|)). The checking
and scaling functions are linear in the size of the graph.
Tips
- Use
MAX_WEIGHT_ASSIGNMENT_T() to compute a maximum weighted
assignment in a bipartite graph.
- If you are determined to use
MAX_WEIGHT_ASSIGNMENT()be
aware of the arithmetic problems that may arise. In case of double
edge weights use MWA_SCALE_WEIGHTS() to modify the edge
weights explicitely.
- Use
CHECK_MAX_WEIGHT_ASSIGNMENT_T() and CHECK_MAX_WEIGHT_ASSIGNMENT()
to ensure the correctness of your result. Checking the result
is much easier than computing a maximum weighted assignment in a bipartite
graph. Therefore, these are less complicated and less error prone. Moreover,
checking is only linear in the size of the graph. So, the overhead is
quite small.
|