comp3530 Assignment 5 s2 2016
This assignment is due on Nov 12. All submitted work must be done individually
without consulting someone else’s solutions in accordance with the University’s
“Academic Dishonesty and Plagiarism” policies.
Problem 1. Let f and g be two subset functions over a common ground set U.
Consider the following functions:
h1(S) = f (S)g(S) for all S ⊆ U, anda)
h2(S) =
√
f (S) for all S ⊆ U.b)
For each function hi prove or disprove that hi is submodular whenever f and g
are normalized, monotone non-decreasing, and submodular.
Problem 2. Consider an instance of the knapsack problem where we have n items
with weight w1, . . . , wn and benefit b1, . . . , bn, and knapsack with capacity W. For
a set S ⊆ {1, . . . , n} let f (S) be the value of the knapsack problem restricted to the
items in S; namely, f (S) = max
(
∑
i∈A
bi : A ⊆ S and ∑
i∈A
wi ≤ W
)
.
Prove that f is not submodular.
Problem 3. Let T be a rooted tree having node weights w : V → R+. For a non-
empty set S ⊂ V let A(S) be the set ancestors of any node is S, and let C(S) be the
set of common ancestors to all nodes in S. Finally, we define A(∅) = C(∅) = ∅.
Notice that these sets are always non-empty if S ̸= ∅ because the root of T is an
ancestor to all nodes in V (we consider a node to be an ancestor of itself).
Let f (S) = ∑u∈A(S) w(u) and g(S) = ∑u∈C(S) w(u). Prove or disprove that these
functions are submodular.
Problem 4. Let G = (V, E) be a strongly connected directed graph. We define an
alternative cascading process via an iterative process. Starting from A0 = ∅ and
A1 = S, where S is our target set, we define Ai+1 = Ai ∪ Nout(Ai)1 for i > 1.
For v ∈ V let τv to be the index of the first A-set containing v; i.e., v ∈ Aτv and
v /∈ Aτv−1. Since G is strongly connected tv is well-defined for all S ̸= ∅.
We define the average cover time of V from S ̸= ∅ to be
f (S) =
1
|V| ∑v∈V
τv.
To complete the function, we define f (∅) = ∞.
Prove that f is monotone non-increasing and supermodular.
1Recall that Nout(X) = {u ∈ V : ∃(x, u) ∈ E and x ∈ X} is the out neighborhood of X
1
https://sydney.edu.au/students/academic-dishonesty.html