What is the definition of an "orthogonal greedy algorithm"?

What is the definition of a "relaxed greedy algorithms"?

Can you give an example to illustrate how these notions differ from ordinary greedy algorithms?

Wikipedia's article on greedy algorithms says:

There are a few variations to the greedy algorithm:

  • Pure greedy algorithms
  • Orthogonal greedy algorithms
  • Relaxed greedy algorithms

Wikipedia does not explain further or provide any examples, so it's not clear what the Wikipedia article is referring to.

  • 1
    $\begingroup$ You question is too broad and most likely to be closed. Do you have a problem with a specific greedy algorithm ? $\endgroup$ – sashas Nov 19 '15 at 3:43
  • 4
    $\begingroup$ I think this is a fair question. Looking at the Wikipedia article, it is indeed not-at-all-clear what the heck the Wikipedia article is referring to. My working guess would be that this was just a bad edit to the Wikipedia article. It happens sometimes. @iluvAS, to make the question better, you could edit it to describe what research you've done. (Hopefully you've done some additional research beyond just reading the Wikipedia article; you could tell us what you've done and where you've looked, and that might help others who stumble across the same question and save answerers some time.) $\endgroup$ – D.W. Nov 19 '15 at 6:05
  • 2
    $\begingroup$ Asking for one term after the other might make for more focused questions. I think in this case, since they appear together, asking three questions at once is okay. Depending on how diligent the person who wrote this passage was, the answers may be linked, anyway. $\endgroup$ – Raphael Nov 19 '15 at 9:08
  • 2
    $\begingroup$ The terms appear to be defined in this article. $\endgroup$ – Tom van der Zanden Nov 19 '15 at 10:50
  • 2
    $\begingroup$ @TomvanderZanden I think you should post that as an answer, in slightly expanded form! $\endgroup$ – Raphael Nov 19 '15 at 11:48

I have no clue what these various types are. You might want to ask the Wikipedia author who added these types, Wleizero. I can add to the list other types, such as double greedy algorithms, randomized greedy algorithms, reverse delete algorithms, and probably many more.

There are several frameworks for greedy algorithms which might interest you, for example priority algorithms studied by Allan Borodin and his coauthors. However, a laundry list of algorithms does not make a classification. I suggest you just ignore this list of types.

  • $\begingroup$ See Tom van der Zanden's comment for what Wleizero referred to: specific algorithms in some specific (but broad) context. $\endgroup$ – Yuval Filmus Nov 19 '15 at 13:00

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.