Assignments and Matchings Match workers to jobs, etc



Download 231.73 Kb.
Page1/2
Date26.04.2018
Size231.73 Kb.
#46865
  1   2
Assignments and Matchings

Match workers to jobs, etc.

Two types of problems

1. Cardinality

Find matching with maximum number of arcs

2. Weighted problem

Weight on each arc

Find match with greatest total weight


What is the relationship between the cardinality problem and the weighted cardinality problem?

We only consider perfect matches: Ones in which in a match each node is incident to exactly one arc.

Start with bipartite graphs

N1 N2 all arcs (i, j) i  N1 j  N2

Read the applications in section 12.2


Bipartite Cardinality Match

G= (N1  N2, A)

If the graph is undirected make it directed with all arcs going from N1 to N2


1 1


.

.

.

.

.

.
2 2

n1 n2




1 1

S
.



.

.

.

.

.
2 2 t

n1 n2

Solve a maximum flow problem from s to t.
Can show a 1-1 correspondence with the original problem.

Can solve in O(m(n)1/2)



Bipartite weighted matching problem
G= (N1  N2, A) |N1| = |N2|
Find a perfect match with minimum weight
If:

1. directed iN1 jN2 all (i,j)



2. undirected, convert to directed by requiring the arcs to go from N1 to N2

It is equivalent to an Assignment Problem

Min




Download 231.73 Kb.

Share with your friends:
  1   2




The database is protected by copyright ©ua.originaldll.com 2024
send message

    Main page