# 代写代考 COMP3530 Maximum submodular coverage – cscodehelp代写

Maximum submodular coverage
This week we study the maximum submodular coverage problem, a generalization of the maximum coverage problem. We also intro- duce the concept of approximation algorithms.
11.1 Maximum coverage
We start by discussing the maximum coverage problem. Given a collection of subsets S = {S1,…,Sm} of a ground set U, we want to pick k subsets whose union has maximum cardinality:
maximize 􏰣􏰣􏰤T∈C T 􏰣􏰣 such that C ⊆ S and |C| = k
The problem is known to be NP-hard, so we will design an ap-
proximation algorithm for it.
Definition 11.1. For a maximization problem, a ρ-approximation is an algorithm that runs in polynomial time and returns a solution whose cost is at least ρ times the cost of an optimal solution, where ρ ≤ 1.
For minimization problems, we define a ρ-approximation to be an algorithm that runs in polynomial time and returns a solution whose cost is at most ρ times the cost of the optimum, where ρ ≥ 1.
Consider the following greedy algorithm that builds a solution by iteratively picking the set maximizing the number of newly covered elements.
The algorithm is too shortsighted to be able to find an optimal solution in general, but it is good approximation.
In general, greedy is not optimal. In the above instance, if k = 2, greedy may pick S3 and S1 covering 1.5l elements, while the optimal solution uses S1 and S2 to cover 2l elements.
1: 2: 3: 4: 5: 6:
functiongreedy(k,U,S) C←∅
while |C| < k do let S ∈ S be a subset maximizing 􏰣􏰣S􏰤T∈C T 􏰣􏰣 add S to C This work is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License. week 11 – maximum submodular coverage discrete optimization 2 Theorem 11.1. Algorithm greedy is a 􏰊1 − e1 􏰋-approximation for the maximum coverage problem. Let O1,O2,...,Ok be the subsets used by an optimal solution, Recall that e ≈ 2.718 is a mathematical constant that pops up in many places, such as i) e = 􏰅∞ 1 , n=1 n! and let opt be the value of the optimal solution; that is, opt = 􏰤􏰦n | j Oj|. Similarly, let A1,A2,...,Ak be the sets chosen by greedy iii) e is such that e 1 dx = 1, 􏰤i 1x sortedintheordertheyarechosen.Finally,letXi= j=1Aj. We start by noting that the first subset chosen by the algorithm must have maximum cardinality among all subsets, in particular |A1| ≥ |Oj| for all j = 1,...,k. Therefore, iv) n!=√2πn􏰈n􏰉n􏰈1+O(1)􏰉, en |X1| ≥ max|Oj| ≥ j j ≥ opt. and many others. Here we use the fact that the cardinal- ity of the union of two sets is less than or equal to the sum of the cardinalities of the two sets. ii) e = limn→∞ 􏰈1 + 1 􏰉n, Now, for the second subset we note that | A2 X1| ≥ |Oj X1| for all j = 1,...,k. Therefore, |A2X1|≥max|OjX1|≥ j j 1 ≥ j j 1 ≥ opt−|X1|, 􏰅 |O X | |􏰈􏰤 O 􏰉X | jkkk opt+(k−1)|X1| opt 􏰙 k−1􏰚 |X2|=|X1|+|A2X1|≥ k ≥ k 1+ k Using induction and following a similar line of reasoning, one can prove that for all i = 1,...,k we have opt 􏰀 k−1 􏰙k−1􏰚i−1􏰁 |Xi|≥ k 1+ k +···+ k . To finish off the proof of the theorem, we just need to note that opt 􏰀 k−1 􏰙k−1􏰚k−1􏰁 |Xk|≥ k 1+ k +···+ k Here we use the fact that a geometric series collapses to 2 l 1−al+1 1+a+a +···+a = 1−a . and that the series 􏰈1 − n1 􏰉n is increas- ing and converges to 1e . 􏰀 􏰙 1􏰚k􏰁 =opt 1− 1−k , >opt1−lim 1− n→∞
􏰙 1􏰚 =opt1− .
􏰈 1 − n1 􏰉 n n
11.2 Maximum submodular coverage
Given a subset function f : 2U → R defined on the power set of a ground set U, we consider the problem of finding a subset C of cardinality k maximizing f; that is,
maximize f(C) such that C ⊆ U and |C| ≤ k. (11.1)
Definition 11.2. A function f : 2U → R is monotone non-decreasing if ∀A⊆B⊆U : f(A)≤f(B).
week 11 – maximum submodular coverage
discrete optimization 3
Definition 11.3. A function f : 2U → R is submodular if f(A+x)−f(A) ≥ f(B+x)−f(B)∀A ⊆ B ⊆ U,x ∈ UB.
Definition 11.4. A function f : 2U → R is normalized if f(∅) = 0.
When the function f in (11.1) is monotone non-decreasing, sub- modular, and normalized we call (11.1) the maximum submodular coverage problem. In this section we study the following simple greedy algorithm that builds a solution by iteratively picking an element maximizing the increase in f value.
Given an instance of the maximum coverage problem (k′, U′, S ′), where S′ = {S1,…,Sm)}, we can construct an instance (k, U, f) of maximum submodular coverage by defining
U = {1,…,m}, and f(C) = 􏰣􏰣 􏰤i∈C Si 􏰣􏰣.
The function f is monotone non- decreasing and submodular.
Note that greedy and greedy- submodular behave exactly the same way on (k′,U′,S′) and (k,U,f), so we can regard Theorem 11.2 as a strict generalization of Theorem 11.1.
1: 2: 3: 4: 5: 6:
functiongreedy-submodular(k,U,f) C←∅