CODEWITHSUNDEEP
algorithm
Andrew Tomazos
Andrew Tomazos

Reputation: 68638

Algorithm to max(min(matching))?

Given two sets A and B of equal size N, and a weighting assigning a real number to each of the N^2 entries of the cross-product AxB, we want to form a matching of A and B such that the lowest weighting is maximized.

Take as an example we are organizing a horse race and we have 10 jockeys and 10 horses, each jockey has a different expected speed riding each horse. We have to pick which jockey rides which horse such that the slowest jockey/horse of this match-up, is as fast as possible.

Take 

    i  j  k
a   9  1  2
b   4  3  1
c   7  3  5

Here the "max-min-matching" is { (a,i), (b,j), (c,k) } with a value of 3.

What is an algorithm to calculate this matching and what is its complexity?

Upvotes: 1

Views: 578

Answers (3)

Osman Ay
Osman Ay

Reputation: 1

Binary search on the result (max-min edge cost). Use max flow min cost algorithm to validate the current edge cost.

Upvotes: 0

amit
amit

Reputation: 178441

This answer guides how to create an O(n^2 * sqrt(n) * log(n)) solution for this problem.

Naive slow algorithm:
First, note that a naive O(n^4 * sqrt(n)) is iteratively using a matching algorithm on the bipartite graph which models the problem, and looking for the "highest set of edges" that cannot be remvoed. (Meaning: looking for the maximal edge that will be minimal in a matching).

The graph is G= (V,E), where V = A [union] B and E = A x B.

The algorithm is:

sort the edges according to the weighted value
while there is an unweighted match match:
   remove the edge with smallest value
return the match weight of the last removed edge

Correctness explanation:
It is easy to see that the value is not smaller then the last removed edge - because there is a match using it and not "smaller" edge.
It is also not higher because when this edge is removed - there is no match.

complexity:
running O(n^2) the matching algorithm, which is O(|E|sqrt(|V|)) = O(n^2 * sqrt(n)) yields total of O(n^4 * sqrt(n)

We would like to reduce the O(n^2) factor, since the matching algorithm should probably be used.

Optimizing:
Note that the algorithm is actually looking where to "cut" the list of sorted edges. We are actually looking for the smallest edge that must be in the list in order to obtain a match.
One can imply binary search here, where each "compare" is actually checking if there is a matching, and you are looking for the "highest" element that yields a match. This will result in O(log(n^2)) = O(logn) iterations of the matching algorithm, giving you total of O(n^2 * sqrt(n) * log(n))

high level optimized algorithm:

//the compare OP
checkMatching(edges,i): 
   edges' <- edges 
   remove from edges' all the elements with index j < i
   check if there is a match in the graph
   return 1 if there is, 0 otherwise.
//the algorithm:
find max_min(vertices,edges):
   sort edges according to weight ascending
   binary search in edges for the smallest index that yields 0
   let this index be i
   remove from edges all the elements with index j < i
   return a match with the modified edges

Upvotes: 2

Allen Koo
Allen Koo

Reputation: 2096

This problem is a typical Bipartite Matching problem. You can have look at the Hungarian method or KM algorithm to solve it.

Upvotes: 0

Related Questions