10/30/22, 5:19 PM L10: Submodularity of Objective Function: Network Science – CS-7280-O01
L10: Submodularity of Objec ve Func on
The function we try to maximize, f(S), is nonlinear and it obviously depends on the topology of the network as well as on the specific diffusion model.
As we will see at the next page, however, the function f(S) has an interesting property referred to as “submodularity”.
Copyright By PowCoder代写 加微信 powcoder
In this page, we first define submodularity – and then state an important result on how to optimize such functions.
Suppose that a function f(X) maps a finite subset X of elements from a ground set U to non-negative real numbers.
The function f(X) is called monotone if
The function f(X) is called submodular if it satisfies the following “diminishing
returns” property:
In other words, the marginal gain from adding an element v to a set X is at least as high as the marginal gain from adding the same element to a superset T of X.
https://gatech. instructure. com/courses/265324/pages/l10-submodularity-of-objective-function?module_item_id=2520832 1/2
10/30/22, 5:19 PM L10: Submodularity of Objective Function: Network Science – CS-7280-O01
Dr. Nemhauser (a professor at Georgia Tech) and his colleagues proved the following facts about monotone and submodular functions:
The bad news: optimizing such functions, subject to the constraint that X includes k elements, is an NP-Hard problem, and so it cannot be solved efficiently by any algorithm (unless if P=NP).
The good news: Consider an iterative greedy heuristic that adds one element in X in each iteration, selecting the element that gives the maximum increase in f(X). This simple algorithm has an approximation ratio . This means that the greedy solution cannot be worse than about 63% of the optimum value of f(X).
The previous result is very important in practice because it means that, even though the greedy algorithm is suboptimal, we have a reasonable bound on its distance from the optimal solution.
Food For Thought
Prove that a non-negative linear combination of a set of submodular functions is also a submodular function.
https://gatech. instructure. com/courses/265324/pages/l10-submodularity-of-objective-function?module_item_id=2520832 2/2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com