Talk:Submodular set function

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

Why would a submodular function be necessarily a subadditive function? I believe it requires nonnegativity. Peleg (talk) 15:16, 17 December 2011 (UTC)Reply

Agreed. Somehow this point skipped my mind, since most submodular functions considered are nonnegative. But I have edited it to reflect this. Anonash (talk) 05:54, 10 February 2012 (UTC)Reply

Introductory lines of the topic, or the topic definition is very difficult to comprehend. It must be splitted into short sentences. Especially this part is quite confusing: "that the difference in the value of the function that a single element makes "

Difference between current value of the function and previous value after adding new item????? — Preceding unsigned comment added by Osmankhalid2005 (talk • contribs) 18:23, 11 March 2013 (UTC)Reply

"has the property that the difference in the incremental value of the function that a single element makes when added to an input set *decreases* as the size of the input set increases." I am not expert, but should not this be:

"has the property that the difference in the incremental value of the function that a single element makes when added to an input set *does not increase* as the size of the input set increases." — Preceding unsigned comment added by 84.182.57.56 (talk) 16:40, 17 March 2019 (UTC)Reply

Formally yes, but such a wording sounds more ambiguous to me, as it could also be interpreted as "does not always increase", while the current wording is good enough for the lead. Tokenzero (talk) 20:31, 17 March 2019 (UTC)Reply

Note that it says decrease, and not strictly decrease. I see though how the sentence can be confusing. How about this replacement: "In mathematics, a submodular set function (also known as a submodular function) is a set function who, informally, has the following property: the incremental value of adding a single element to the input decreases as the size of the input set increases." --Hous21 (talk) 20:37, 17 March 2019 (UTC)Reply