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$

3 Answers 3

1
$\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$ While the selection of GS looks at first sight greedy, this is not true, as later, the algorithm might modify such an assignment from before. In greedy algorithms such a refinement/modification usually is not taken (e.g., Dijkstra who does not modify the greedy decision). In some sense one might compare GS to BF-algorithm then who is also not greedy. $\endgroup$
    – Arne
    Oct 24, 2022 at 12:41
2
$\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$
3
  • $\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, 2017 at 16:00
  • 1
    $\begingroup$ Well, it's not my fault that your professor made a mistake. Don't blame the messenger. $\endgroup$ Dec 1, 2017 at 16:01
  • 1
    $\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$ Dec 1, 2017 at 16:02
1
$\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 and acknowledge you have read our privacy policy.

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