1
$\begingroup$

Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.

$\endgroup$
2
$\begingroup$

If you consider the Gale–Shapley algorithm, it takes a greedy approach.

By the definition of Wikipedia:

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

The Gale-Shapley Algorithm does exactly that. At each step, the 'proposers' take a greedy decision of selecting the best partner (locally optimal choice) that was not yet proposed.

$\endgroup$
1
$\begingroup$

Problems are not greedy or dynamic. Algorithms might use a greedy heuristic or the dynamic programming paradigm.

The usual algorithm for solving the stable matching problem is iterative, and so fits to neither the greedy paradigm nor the dynamic programming paradigm. You might as well have asked whether quicksort were greedy or dynamic programming.

$\endgroup$
  • $\begingroup$ Ya, but I am a student and this was the question asked to me in an exam and I had to state whether the answer is true or false. Please help if you can @Yuval Filmus $\endgroup$ – AlgoMan Dec 1 '17 at 16:00
  • $\begingroup$ Well, it's not my fault that your professor made a mistake. Don't blame the messenger. $\endgroup$ – Yuval Filmus Dec 1 '17 at 16:01
  • $\begingroup$ We're not here to solve past exams. We're here to help you understand the material. That's beyond guessing the correct answer to a faulty question. $\endgroup$ – Yuval Filmus Dec 1 '17 at 16:02
0
$\begingroup$

If you are asking about the Gale-Shapley algorithm, GS algorithm is not greedy.

A greedy algorithm is one that does not change its decision once made.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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