Mixing
Proof that my greedy algorithm for assigning candidates to jobs works
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I was using the answers on this question as a guide for proving that my greedy algorithm is correct. (Unfortunately, CS Stack Exchange does not accept proof verification questions, which is why I posted this here rather than there).
The full code (along with my empirical testing comparing its output to Simplex) can be found on Code Review SE here.
The original problem was basically as follows (and this is the same as my Code Review SE description):
A matchmaker is working with six clients: John, Joe, Charlie, Jill, Leslie, and Katie. John is compatible with Jill and Leslie, Joe is compatible with Jill. Charlie is compatible with Jill, Leslie, and Katie. How should the matchmaker match them to have the fewest unmatched people (subject to the constraint that only compatable people can be matched)?
This is kind of like the Stable Marriage Problem in a way, except simpler because there's no notion of preference. If John is compatible with both Jill and Leslie, there isn't any preference for one vs. the other. This actually has some implications for the proof because there's no guarantee that optimal solutions are unique.
In my other post, I describe my algorithm as follows:
My idea to solve this was that you should start with the person who has the fewest compatibilities, and match them with the person that they're connected to that has the fewest compatibilities. For example, since Joe is only connected with Jill, you should match them first. Since John is compatible with both Jill and Leslie, he should be matched next. Since Jill is already matched, he must be matched with Leslie. Finally, since Charlie is compatible with the most people, he's matched last.
For my project, I'm doing the same thing, except showing various methods to assign candidates to jobs.
Here's the proof I have so far that this algorithm works:
Let S be the solution outputted by my algorithm for “matches†on the connected bipartite graph $G=(U,V,E)$. (I specify that the graph is connected because each job has at least one candidate that “match†it, and each candidate is a “match†for at least one job).
$G$ could be a complete bipartite graph, but there’s no guarantee of that. (If it was a complete bipartite graph, the problem would be trivial and you could do whatever assignment you wanted).
A “match†is defined as the assignment of candidate x to job y, where $x in U, y in V$ and $x$ and $y$ are connected by some edge $e in E$. Note that edges only connect candidates to jobs, not jobs to other jobs or candidates to other candidates, so the fact that $x$ and $y$ are connected by $e$ guarantees that one is a job and the other is a candidate. Without loss of generality, we will call the candidate $x$ and the job $y$.
Note that if all of the jobs have a candidate assigned to them, or all of the candidates are assigned to jobs, the proof is trivial because this assignment is trivially optimal: by the Pigeonhole Principle, there is no way to hire more people than we’ve already assigned. The case that we even need a proof for is if there are both candidates that aren’t hired and unfilled jobs; if there are no unfilled jobs or no unhired candidates, we obviously can’t possibly do any better.
The fact that an optimal solution exists is guaranteed by the fact that the graph is connected: clearly, it’s possible to assign at least one candidate to at least one job (or the graph wouldn’t even be connected). If it’s possible to assign more candidates to more jobs, then the solution that has the greatest number of candidates in the greatest number of jobs is the best solution.
Let $P$ be the set of optimal solutions (each problem could have several optimal solutions – I separately gave examples of that type of a situation), $O in P$ be an arbitrary optimal solution, and S be the actual solution. If $S notin P$ (i.e. $S$ is not one of the optimal solutions), then it must be the case that we can construct another solution $O$ which has an even greater number of candidates assigned to jobs. Also, $|S|<|O|$ (i.e. $O$ fills more of the jobs than $S$).
Note at this point that all optimal solutions have the same number of matches (but are not guaranteed to be unique – i.e. there could be several equally optimal matchings), and that if our solution is suboptimal it must differ from all of them in some step. Let $i$ be the index of the first iteration where $(x,y) notin O$ (i.e. where this step differs from all optimal solutions).
This means that we have $$S = (x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n)$$
Since $i$ is minimal, it must be the case that
$$(x_1, y_1), ..., (x_i - 1, y_i - 1) in O$$
(i.e. that that portion of our solution is part of an optimal solution).
In particular, the optimal solution $O$ is:
$$O = (x_1, y_1), (x_2, y_2), ..., (x_i-1, y_i-1), (x^prime_i, y^prime_i), (x^prime_i+1, y^prime_i + 1), ...,(x^prime_n, y^prime_n)$$
Note that we've established that the first $i - 1$ items of $O$ are the same as what my algorithm would generate. That being said, $C_x_1 le C_x_2 le ... le C_x_i - 1$, where $C_x_1$, for example, is all of the jobs that candidate $x_1$ is compatable with.
Note, too, that since $x_i$ is different than what my algorithm would've generated, it must be the case that $C_x_i < C_x_i + 1$ (because my algorithm would've selected $x_i$ such that $C_x_i + 1 < C_x_i$).
At this point, I assert that selecting $x_i$ and $x_i + 1$ such that $C_x_i < C_x_i+1$ will never be a better choice (although it might be an equally good choice, since there's no guarantee that the optimal solution will be unique) because the fact that $C_x_i < C_x_i+1$ actually guarantees that we will have fewer choices as to how to assign the remaining candidates; thus, future assignments of candidates to jobs will be no better than ours (and possibly worse). But this contradicts the premise that $O$ is a better assignment than $S$.
Any thoughts on this? Is this proof correct?
combinatorics proof-verification optimization algorithms
asked Aug 6 at 2:18
EJoshuaS
425619
add a comment |Â
up vote
2
down vote
favorite
I was using the answers on this question as a guide for proving that my greedy algorithm is correct. (Unfortunately, CS Stack Exchange does not accept proof verification questions, which is why I posted this here rather than there).
The full code (along with my empirical testing comparing its output to Simplex) can be found on Code Review SE here.
The original problem was basically as follows (and this is the same as my Code Review SE description):
A matchmaker is working with six clients: John, Joe, Charlie, Jill, Leslie, and Katie. John is compatible with Jill and Leslie, Joe is compatible with Jill. Charlie is compatible with Jill, Leslie, and Katie. How should the matchmaker match them to have the fewest unmatched people (subject to the constraint that only compatable people can be matched)?
This is kind of like the Stable Marriage Problem in a way, except simpler because there's no notion of preference. If John is compatible with both Jill and Leslie, there isn't any preference for one vs. the other. This actually has some implications for the proof because there's no guarantee that optimal solutions are unique.
In my other post, I describe my algorithm as follows:
My idea to solve this was that you should start with the person who has the fewest compatibilities, and match them with the person that they're connected to that has the fewest compatibilities. For example, since Joe is only connected with Jill, you should match them first. Since John is compatible with both Jill and Leslie, he should be matched next. Since Jill is already matched, he must be matched with Leslie. Finally, since Charlie is compatible with the most people, he's matched last.
For my project, I'm doing the same thing, except showing various methods to assign candidates to jobs.
Here's the proof I have so far that this algorithm works:
Let S be the solution outputted by my algorithm for “matches†on the connected bipartite graph $G=(U,V,E)$. (I specify that the graph is connected because each job has at least one candidate that “match†it, and each candidate is a “match†for at least one job).
$G$ could be a complete bipartite graph, but there’s no guarantee of that. (If it was a complete bipartite graph, the problem would be trivial and you could do whatever assignment you wanted).
A “match†is defined as the assignment of candidate x to job y, where $x in U, y in V$ and $x$ and $y$ are connected by some edge $e in E$. Note that edges only connect candidates to jobs, not jobs to other jobs or candidates to other candidates, so the fact that $x$ and $y$ are connected by $e$ guarantees that one is a job and the other is a candidate. Without loss of generality, we will call the candidate $x$ and the job $y$.
Note that if all of the jobs have a candidate assigned to them, or all of the candidates are assigned to jobs, the proof is trivial because this assignment is trivially optimal: by the Pigeonhole Principle, there is no way to hire more people than we’ve already assigned. The case that we even need a proof for is if there are both candidates that aren’t hired and unfilled jobs; if there are no unfilled jobs or no unhired candidates, we obviously can’t possibly do any better.
The fact that an optimal solution exists is guaranteed by the fact that the graph is connected: clearly, it’s possible to assign at least one candidate to at least one job (or the graph wouldn’t even be connected). If it’s possible to assign more candidates to more jobs, then the solution that has the greatest number of candidates in the greatest number of jobs is the best solution.
Let $P$ be the set of optimal solutions (each problem could have several optimal solutions – I separately gave examples of that type of a situation), $O in P$ be an arbitrary optimal solution, and S be the actual solution. If $S notin P$ (i.e. $S$ is not one of the optimal solutions), then it must be the case that we can construct another solution $O$ which has an even greater number of candidates assigned to jobs. Also, $|S|<|O|$ (i.e. $O$ fills more of the jobs than $S$).
Note at this point that all optimal solutions have the same number of matches (but are not guaranteed to be unique – i.e. there could be several equally optimal matchings), and that if our solution is suboptimal it must differ from all of them in some step. Let $i$ be the index of the first iteration where $(x,y) notin O$ (i.e. where this step differs from all optimal solutions).
This means that we have $$S = (x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n)$$
Since $i$ is minimal, it must be the case that
$$(x_1, y_1), ..., (x_i - 1, y_i - 1) in O$$
(i.e. that that portion of our solution is part of an optimal solution).
In particular, the optimal solution $O$ is:
$$O = (x_1, y_1), (x_2, y_2), ..., (x_i-1, y_i-1), (x^prime_i, y^prime_i), (x^prime_i+1, y^prime_i + 1), ...,(x^prime_n, y^prime_n)$$
Note that we've established that the first $i - 1$ items of $O$ are the same as what my algorithm would generate. That being said, $C_x_1 le C_x_2 le ... le C_x_i - 1$, where $C_x_1$, for example, is all of the jobs that candidate $x_1$ is compatable with.
Note, too, that since $x_i$ is different than what my algorithm would've generated, it must be the case that $C_x_i < C_x_i + 1$ (because my algorithm would've selected $x_i$ such that $C_x_i + 1 < C_x_i$).
At this point, I assert that selecting $x_i$ and $x_i + 1$ such that $C_x_i < C_x_i+1$ will never be a better choice (although it might be an equally good choice, since there's no guarantee that the optimal solution will be unique) because the fact that $C_x_i < C_x_i+1$ actually guarantees that we will have fewer choices as to how to assign the remaining candidates; thus, future assignments of candidates to jobs will be no better than ours (and possibly worse). But this contradicts the premise that $O$ is a better assignment than $S$.
Any thoughts on this? Is this proof correct?
combinatorics proof-verification optimization algorithms
asked Aug 6 at 2:18
EJoshuaS
425619
This is a little nitpicky, but your objective seems underspecified. "How should the matchmaker match them to have the fewest unmatched people?" The correct answer to this is to match them all arbitrarily. I suppose you want to include the assumption that the matchmaker can only match compatible pairs.
– Theoretical Economist
Aug 6 at 2:33
@TheoreticalEconomist Good point, actually. I edited to explicitly state that constraint.
– EJoshuaS
Aug 6 at 2:36
2
This is unweighted bipartite matching, and you can get a maximal matching with your favorite max flow algorithm.
– saulspatz
Aug 6 at 2:59
1
The Edmond's Blossom Algorithm is a classic algorithm for this problem. There are improved variants, such as the Hopcroft-Karp algorithm. Max-Flow algorithms also work well to find maximum matchings in bipartite graphs.
– ml0105
Aug 6 at 5:09
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I was using the answers on this question as a guide for proving that my greedy algorithm is correct. (Unfortunately, CS Stack Exchange does not accept proof verification questions, which is why I posted this here rather than there).
The full code (along with my empirical testing comparing its output to Simplex) can be found on Code Review SE here.
The original problem was basically as follows (and this is the same as my Code Review SE description):
A matchmaker is working with six clients: John, Joe, Charlie, Jill, Leslie, and Katie. John is compatible with Jill and Leslie, Joe is compatible with Jill. Charlie is compatible with Jill, Leslie, and Katie. How should the matchmaker match them to have the fewest unmatched people (subject to the constraint that only compatable people can be matched)?
This is kind of like the Stable Marriage Problem in a way, except simpler because there's no notion of preference. If John is compatible with both Jill and Leslie, there isn't any preference for one vs. the other. This actually has some implications for the proof because there's no guarantee that optimal solutions are unique.
In my other post, I describe my algorithm as follows:
My idea to solve this was that you should start with the person who has the fewest compatibilities, and match them with the person that they're connected to that has the fewest compatibilities. For example, since Joe is only connected with Jill, you should match them first. Since John is compatible with both Jill and Leslie, he should be matched next. Since Jill is already matched, he must be matched with Leslie. Finally, since Charlie is compatible with the most people, he's matched last.
For my project, I'm doing the same thing, except showing various methods to assign candidates to jobs.
Here's the proof I have so far that this algorithm works:
Let S be the solution outputted by my algorithm for “matches†on the connected bipartite graph $G=(U,V,E)$. (I specify that the graph is connected because each job has at least one candidate that “match†it, and each candidate is a “match†for at least one job).
$G$ could be a complete bipartite graph, but there’s no guarantee of that. (If it was a complete bipartite graph, the problem would be trivial and you could do whatever assignment you wanted).
A “match†is defined as the assignment of candidate x to job y, where $x in U, y in V$ and $x$ and $y$ are connected by some edge $e in E$. Note that edges only connect candidates to jobs, not jobs to other jobs or candidates to other candidates, so the fact that $x$ and $y$ are connected by $e$ guarantees that one is a job and the other is a candidate. Without loss of generality, we will call the candidate $x$ and the job $y$.
Note that if all of the jobs have a candidate assigned to them, or all of the candidates are assigned to jobs, the proof is trivial because this assignment is trivially optimal: by the Pigeonhole Principle, there is no way to hire more people than we’ve already assigned. The case that we even need a proof for is if there are both candidates that aren’t hired and unfilled jobs; if there are no unfilled jobs or no unhired candidates, we obviously can’t possibly do any better.
The fact that an optimal solution exists is guaranteed by the fact that the graph is connected: clearly, it’s possible to assign at least one candidate to at least one job (or the graph wouldn’t even be connected). If it’s possible to assign more candidates to more jobs, then the solution that has the greatest number of candidates in the greatest number of jobs is the best solution.
Let $P$ be the set of optimal solutions (each problem could have several optimal solutions – I separately gave examples of that type of a situation), $O in P$ be an arbitrary optimal solution, and S be the actual solution. If $S notin P$ (i.e. $S$ is not one of the optimal solutions), then it must be the case that we can construct another solution $O$ which has an even greater number of candidates assigned to jobs. Also, $|S|<|O|$ (i.e. $O$ fills more of the jobs than $S$).
Note at this point that all optimal solutions have the same number of matches (but are not guaranteed to be unique – i.e. there could be several equally optimal matchings), and that if our solution is suboptimal it must differ from all of them in some step. Let $i$ be the index of the first iteration where $(x,y) notin O$ (i.e. where this step differs from all optimal solutions).
This means that we have $$S = (x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n)$$
Since $i$ is minimal, it must be the case that
$$(x_1, y_1), ..., (x_i - 1, y_i - 1) in O$$
(i.e. that that portion of our solution is part of an optimal solution).
In particular, the optimal solution $O$ is:
$$O = (x_1, y_1), (x_2, y_2), ..., (x_i-1, y_i-1), (x^prime_i, y^prime_i), (x^prime_i+1, y^prime_i + 1), ...,(x^prime_n, y^prime_n)$$
Note that we've established that the first $i - 1$ items of $O$ are the same as what my algorithm would generate. That being said, $C_x_1 le C_x_2 le ... le C_x_i - 1$, where $C_x_1$, for example, is all of the jobs that candidate $x_1$ is compatable with.
Note, too, that since $x_i$ is different than what my algorithm would've generated, it must be the case that $C_x_i < C_x_i + 1$ (because my algorithm would've selected $x_i$ such that $C_x_i + 1 < C_x_i$).
At this point, I assert that selecting $x_i$ and $x_i + 1$ such that $C_x_i < C_x_i+1$ will never be a better choice (although it might be an equally good choice, since there's no guarantee that the optimal solution will be unique) because the fact that $C_x_i < C_x_i+1$ actually guarantees that we will have fewer choices as to how to assign the remaining candidates; thus, future assignments of candidates to jobs will be no better than ours (and possibly worse). But this contradicts the premise that $O$ is a better assignment than $S$.
Any thoughts on this? Is this proof correct?
combinatorics proof-verification optimization algorithms
asked Aug 6 at 2:18
EJoshuaS
425619
I was using the answers on this question as a guide for proving that my greedy algorithm is correct. (Unfortunately, CS Stack Exchange does not accept proof verification questions, which is why I posted this here rather than there).
The full code (along with my empirical testing comparing its output to Simplex) can be found on Code Review SE here.
The original problem was basically as follows (and this is the same as my Code Review SE description):
A matchmaker is working with six clients: John, Joe, Charlie, Jill, Leslie, and Katie. John is compatible with Jill and Leslie, Joe is compatible with Jill. Charlie is compatible with Jill, Leslie, and Katie. How should the matchmaker match them to have the fewest unmatched people (subject to the constraint that only compatable people can be matched)?
This is kind of like the Stable Marriage Problem in a way, except simpler because there's no notion of preference. If John is compatible with both Jill and Leslie, there isn't any preference for one vs. the other. This actually has some implications for the proof because there's no guarantee that optimal solutions are unique.
In my other post, I describe my algorithm as follows:
My idea to solve this was that you should start with the person who has the fewest compatibilities, and match them with the person that they're connected to that has the fewest compatibilities. For example, since Joe is only connected with Jill, you should match them first. Since John is compatible with both Jill and Leslie, he should be matched next. Since Jill is already matched, he must be matched with Leslie. Finally, since Charlie is compatible with the most people, he's matched last.
For my project, I'm doing the same thing, except showing various methods to assign candidates to jobs.
Here's the proof I have so far that this algorithm works:
Let S be the solution outputted by my algorithm for “matches†on the connected bipartite graph $G=(U,V,E)$. (I specify that the graph is connected because each job has at least one candidate that “match†it, and each candidate is a “match†for at least one job).
$G$ could be a complete bipartite graph, but there’s no guarantee of that. (If it was a complete bipartite graph, the problem would be trivial and you could do whatever assignment you wanted).
A “match†is defined as the assignment of candidate x to job y, where $x in U, y in V$ and $x$ and $y$ are connected by some edge $e in E$. Note that edges only connect candidates to jobs, not jobs to other jobs or candidates to other candidates, so the fact that $x$ and $y$ are connected by $e$ guarantees that one is a job and the other is a candidate. Without loss of generality, we will call the candidate $x$ and the job $y$.
Note that if all of the jobs have a candidate assigned to them, or all of the candidates are assigned to jobs, the proof is trivial because this assignment is trivially optimal: by the Pigeonhole Principle, there is no way to hire more people than we’ve already assigned. The case that we even need a proof for is if there are both candidates that aren’t hired and unfilled jobs; if there are no unfilled jobs or no unhired candidates, we obviously can’t possibly do any better.
The fact that an optimal solution exists is guaranteed by the fact that the graph is connected: clearly, it’s possible to assign at least one candidate to at least one job (or the graph wouldn’t even be connected). If it’s possible to assign more candidates to more jobs, then the solution that has the greatest number of candidates in the greatest number of jobs is the best solution.
Let $P$ be the set of optimal solutions (each problem could have several optimal solutions – I separately gave examples of that type of a situation), $O in P$ be an arbitrary optimal solution, and S be the actual solution. If $S notin P$ (i.e. $S$ is not one of the optimal solutions), then it must be the case that we can construct another solution $O$ which has an even greater number of candidates assigned to jobs. Also, $|S|<|O|$ (i.e. $O$ fills more of the jobs than $S$).
Note at this point that all optimal solutions have the same number of matches (but are not guaranteed to be unique – i.e. there could be several equally optimal matchings), and that if our solution is suboptimal it must differ from all of them in some step. Let $i$ be the index of the first iteration where $(x,y) notin O$ (i.e. where this step differs from all optimal solutions).
This means that we have $$S = (x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n)$$
Since $i$ is minimal, it must be the case that
$$(x_1, y_1), ..., (x_i - 1, y_i - 1) in O$$
(i.e. that that portion of our solution is part of an optimal solution).
In particular, the optimal solution $O$ is:
$$O = (x_1, y_1), (x_2, y_2), ..., (x_i-1, y_i-1), (x^prime_i, y^prime_i), (x^prime_i+1, y^prime_i + 1), ...,(x^prime_n, y^prime_n)$$
Note that we've established that the first $i - 1$ items of $O$ are the same as what my algorithm would generate. That being said, $C_x_1 le C_x_2 le ... le C_x_i - 1$, where $C_x_1$, for example, is all of the jobs that candidate $x_1$ is compatable with.
Note, too, that since $x_i$ is different than what my algorithm would've generated, it must be the case that $C_x_i < C_x_i + 1$ (because my algorithm would've selected $x_i$ such that $C_x_i + 1 < C_x_i$).
At this point, I assert that selecting $x_i$ and $x_i + 1$ such that $C_x_i < C_x_i+1$ will never be a better choice (although it might be an equally good choice, since there's no guarantee that the optimal solution will be unique) because the fact that $C_x_i < C_x_i+1$ actually guarantees that we will have fewer choices as to how to assign the remaining candidates; thus, future assignments of candidates to jobs will be no better than ours (and possibly worse). But this contradicts the premise that $O$ is a better assignment than $S$.
Any thoughts on this? Is this proof correct?
combinatorics proof-verification optimization algorithms
asked Aug 6 at 2:18
EJoshuaS
425619
edited Aug 6 at 2:36
asked Aug 6 at 2:18
EJoshuaS
425619
asked Aug 6 at 2:18
EJoshuaS
425619
asked Aug 6 at 2:18
EJoshuaS
425619
425619
This is a little nitpicky, but your objective seems underspecified. "How should the matchmaker match them to have the fewest unmatched people?" The correct answer to this is to match them all arbitrarily. I suppose you want to include the assumption that the matchmaker can only match compatible pairs.
– Theoretical Economist
Aug 6 at 2:33
@TheoreticalEconomist Good point, actually. I edited to explicitly state that constraint.
– EJoshuaS
Aug 6 at 2:36
2
This is unweighted bipartite matching, and you can get a maximal matching with your favorite max flow algorithm.
– saulspatz
Aug 6 at 2:59
1
The Edmond's Blossom Algorithm is a classic algorithm for this problem. There are improved variants, such as the Hopcroft-Karp algorithm. Max-Flow algorithms also work well to find maximum matchings in bipartite graphs.
– ml0105
Aug 6 at 5:09
add a comment |Â
This is a little nitpicky, but your objective seems underspecified. "How should the matchmaker match them to have the fewest unmatched people?" The correct answer to this is to match them all arbitrarily. I suppose you want to include the assumption that the matchmaker can only match compatible pairs.
– Theoretical Economist
Aug 6 at 2:33
@TheoreticalEconomist Good point, actually. I edited to explicitly state that constraint.
– EJoshuaS
Aug 6 at 2:36
2
This is unweighted bipartite matching, and you can get a maximal matching with your favorite max flow algorithm.
– saulspatz
Aug 6 at 2:59
1
The Edmond's Blossom Algorithm is a classic algorithm for this problem. There are improved variants, such as the Hopcroft-Karp algorithm. Max-Flow algorithms also work well to find maximum matchings in bipartite graphs.
– ml0105
Aug 6 at 5:09
This is a little nitpicky, but your objective seems underspecified. "How should the matchmaker match them to have the fewest unmatched people?" The correct answer to this is to match them all arbitrarily. I suppose you want to include the assumption that the matchmaker can only match compatible pairs.
– Theoretical Economist
Aug 6 at 2:33
This is a little nitpicky, but your objective seems underspecified. "How should the matchmaker match them to have the fewest unmatched people?" The correct answer to this is to match them all arbitrarily. I suppose you want to include the assumption that the matchmaker can only match compatible pairs.
– Theoretical Economist
Aug 6 at 2:33
@TheoreticalEconomist Good point, actually. I edited to explicitly state that constraint.
– EJoshuaS
Aug 6 at 2:36
@TheoreticalEconomist Good point, actually. I edited to explicitly state that constraint.
– EJoshuaS
Aug 6 at 2:36
2
2
This is unweighted bipartite matching, and you can get a maximal matching with your favorite max flow algorithm.
– saulspatz
Aug 6 at 2:59
This is unweighted bipartite matching, and you can get a maximal matching with your favorite max flow algorithm.
– saulspatz
Aug 6 at 2:59
1
1
The Edmond's Blossom Algorithm is a classic algorithm for this problem. There are improved variants, such as the Hopcroft-Karp algorithm. Max-Flow algorithms also work well to find maximum matchings in bipartite graphs.
– ml0105
Aug 6 at 5:09
The Edmond's Blossom Algorithm is a classic algorithm for this problem. There are improved variants, such as the Hopcroft-Karp algorithm. Max-Flow algorithms also work well to find maximum matchings in bipartite graphs.
– ml0105
Aug 6 at 5:09
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873527%2fproof-that-my-greedy-algorithm-for-assigning-candidates-to-jobs-works%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
This is a little nitpicky, but your objective seems underspecified. "How should the matchmaker match them to have the fewest unmatched people?" The correct answer to this is to match them all arbitrarily. I suppose you want to include the assumption that the matchmaker can only match compatible pairs.
– Theoretical Economist
Aug 6 at 2:33
@TheoreticalEconomist Good point, actually. I edited to explicitly state that constraint.
– EJoshuaS
Aug 6 at 2:36
2
This is unweighted bipartite matching, and you can get a maximal matching with your favorite max flow algorithm.
– saulspatz
Aug 6 at 2:59
1
The Edmond's Blossom Algorithm is a classic algorithm for this problem. There are improved variants, such as the Hopcroft-Karp algorithm. Max-Flow algorithms also work well to find maximum matchings in bipartite graphs.
– ml0105
Aug 6 at 5:09