Hello everyone. Can anyone tell me a real-life problem I've encountered: Summary: Given a graph consisting of 2N vertices and M weighted edges. Find a way to pair N pairs of vertices such that the maximum value of N paired pairs is the smallest.
I have tried to find the optimal solution in polynomial time but can't find it. I plan to use binary search and then recursively go back and forth to generate all possible cases and then get min. Please give me keywords or answers. Sorry for my bad english.
input: 4 10 1 3 4 1 4 3 1 5 2 2 4 5 3 6 1 7 4 3 7 2 1 6 1 3 8 5 5 6 8 3 output: 5
You're right about binary search. Now, when in binary search you need to know whether there exists such a pairing using edges with value $$$\leqslant x$$$, you're actually looking for a perfect matching in a general graph (the one without edges $$$ \gt x$$$). There exist algorithms that can test whether it exists or not in a given graph, but they all are not so simple as Kuhn's algorithm for matchings in bipartite graphs. Still, if you're interested: Blossom shrinking if you're looking for something combinatorial or making use of Tutte's matrix if you're ok with some linear algebra.
Would you please elaborate the real-world application of this problem? Thanks!
It's a simple example. It's like a service to schedule an appointment for soccer matches with a given parameter. and we have overdue match matching feature in our system.
Thank you!