mathematics//optimization//combinatorial optimization//submodular function

A submodular function is a function of sets whose gain from adding one more element shrinks as the set grows, the mathematical form of diminishing returns; its value to an engineer is a guarantee: for a monotone submodular objective, picking elements greedily reaches at least 63 % of the optimum, which justifies the fast greedy placement of sensors, cameras, relay nodes and drones. Monotone means that adding an element never lowers the value.

A submodular function is a function of sets whose gain from adding one more element shrinks as the set grows, the mathematical form of diminishing returns; its value to an engineer is a guarantee: for a monotone submodular objective, picking elements greedily reaches at least 63 % of the optimum, which justifies the fast greedy placement of sensors, cameras, relay nodes and drones. Monotone means that adding an element never lowers the value.

Picture five drones to be stationed over a wildfire so that together their cameras see as much of the front as possible. The first drone goes wherever it sees most. The second adds only what the first does not already cover, so the same spot is worth less to it, and every later drone adds less still. Formally, for sets A⊆BA\subseteq BA⊆B and an element eee outside BBB:

F(A∪{e})−F(A)  ≥  F(B∪{e})−F(B)F(A\cup\{e\})-F(A)\;\ge\;F(B\cup\{e\})-F(B)F(A∪{e})−F(A)≥F(B∪{e})−F(B)

The gain of eee is larger when added to the smaller set. For such an FFF, choosing kkk elements one at a time, each the one that adds most at that moment, gives F(Sgreedy)≥(1−1/e) F(S⋆)≈0.63 F(S⋆)F(S_{\text{greedy}})\ge(1-1/e),F(S^\star)\approx0.63,F(S^\star)F(Sgreedy​)≥(1−1/e)F(S⋆)≈0.63F(S⋆), a result of Nemhauser, Wolsey and Fisher in 1978.

The bound turns a heuristic into an engineering answer: the greedy placement of five drones takes milliseconds and comes with a written guarantee, without ever computing the optimum. The 63 % is a worst case; on real coverage problems greedy usually lands much closer.

Many objectives in sensing are submodular: area covered, the number of targets seen by at least one sensor, and the probability that at least one of several agents succeeds, 1−∏i(1−pi)1-\prod_i(1-p_i)1−∏i​(1−pi​), whose diminishing returns are what makes weapon-target assignment hard for linear methods.

The guarantee has conditions. The 1−1/e1-1/e1−1/e holds for a monotone function under a limit on how many elements are chosen; with other constraints (a budget with unequal costs, a matching) simple greedy guarantees less. An objective with complementarities, where two cameras are worth more together than apart (a stereo pair), is not submodular and greedy can do badly.

The guarantee comes from the objective, and the greedy algorithm only collects it: the same greedy rule that earns 63 % here can be arbitrarily bad on other problems of combinatorial optimization.