Databases Reference
In-Depth Information
to an exponential number of invocations of the algorithm
A
best
for finding the maximum weight
matching. Yet, as we show next, the ideas described above can be used to design a polynomial time
algorithm to find top-
K
matchings.
We apply the dynamic programming technique to make better use of the information ob-
tained from earlier invocations of
A
best
and reduce the number of invocations of
A
best
to be poly-
nomial. Our algorithm is based on solutions to the assignment ranking problem, which involves
the enumeration of
K
assignments with least cost. The first algorithm of
O
K
|
V
|
4
for ranking
assignments was suggested by
Murty
[
1968
], where
is the number of nodes in the assignment
graph.
Hamacher and Queyranne
[
1985/6
] proposed an alternative general algorithm for ranking
solutions of combinatorial problems. This algorithm was later specialized for bipartite matchings
|
V
|
[
Chegireddy and Hamacher
,
1987
]in
O
K
|
V
|
3
, using flow networks.
Pascoal et al.
[
2003
]pre-
sented another
O
K
3
, using a specific order of analyzing assignments.
Our algorithm constructs a tree
T
of invocations of
A
best
. Each node
u
in
T
is associated with
some matching
σ (u)
in
G
and contains specifications of a subset
S
i
(u)
|
V
|
E
of edges that must be
included in
σ (u)
and a subset
S
e
(
u
)
⊆
E
of edges that must be excluded from
σ (u)
. A maximum
weight matching
σ (u)
satisfying these specifications is constructed by the algorithm as follows. The
algorithm first discards the edges of
S
e
from
G
. Then, for each edge
(v
1
,v
2
)
∈
S
i
, the algorithm
discards from
G
edges adjacent either to
v
1
or to
v
2
.Let
G
(u)
be the resulting graph. The algorithm
invokes
A
best
to compute the maximum weight matching
σ
(u)
in
G
(u)
. Finally,
σ (u)
is obtained
from
σ
(u)
by adding edges of
S
i
(u)
. The weight of the matching
σ (u)
is referred to as the weight
of the node
u
and denoted
(u)
.
The algorithm starts by constructing the root
r
of
T
with
S
e
(r)
=∅
⊆
. The root
corresponds to the invocation of
A
best
in the original graph
G
, yielding the maximum weight match-
and
S
i
(r)
=∅
ing
σ(r)
=
σ
1
. Following the notation defined above,
(r)
=
σ
1
. The algorithm expands the
tree iteratively. At each iteration, the algorithm first chooses a leaf to expand. For this purpose, the
algorithm picks the maximum weight leaf over all the leaves of
T
at the current iteration. Let
w
be
the leaf picked by the algorithm and let
σ(w)
be the matching computed by the algorithm for the leaf
w
. Recall that
S
i
(w)
⊆
σ(w)
,
S
e
(w)
∩
σ(w)
=∅
and let
D(w)
=
σ(w)
\
S
i
(w)
and
e
1
,e
2
, ..., e
t
be the edges of
D(w)
. The algorithm builds
t
children of
w
in
T
, denoted
w
1
,w
2
, ..., w
t
. For each
child
w
j
, where
j
=
1
, ..., t
, we define
S
e
w
j
=
S
e
(w)
∪
e
j
S
i
w
j
=
S
i
(w)
∪
j
−
1
l
=
1
{
e
l
}
.
Observe that the definition above ensures that the matchings
σ(w
j
)
,
j
=
1
, ..., t
are pairwise dif-
ferent.
At each iteration
i
, the algorithm outputs the matching
σ(w
j
)
corresponding to the maximum
weight leaf
w
as the
i
-th best matching. The algorithm stops after
K
iterations.
