1
$\begingroup$

The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any existing approaches to find a matching that maximizes the minimum weight? (Can't seem to find any similar references on this)

$\endgroup$

1 Answer 1

1
$\begingroup$

I believe this is known as the "bottleneck matching" problem. Here is an algorithm for that problem.

There is a straightforward algorithm. Pick a threshold $t$. Delete all edges with weight below $t$ and check whether there is a matching in that graph. Now do binary search on $t$, to find the largest $t$ such that the resulting graph has a matching. This requires $O(\lg n)$ executions of a graph matching algorithm, and thus can be done in polynomial time.

I think there may be dedicated algorithms in the literature that may be even faster, but I'm not knowledgeable abou that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.