Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 1 / e

Solution

T = {x_{1}, \dots, x_{n}}

P_{j} = {x_{1}, \dots, x_{j}}

with

P_{0} = \emptyset

, and put

a_{j} = f (P_{j}) - f (P_{j - 1})

. For each

U \subseteq T

, reveal its elements in this same order. Since

U \cap P_{j - 1} \subseteq P_{j - 1}

f (U) = \sum_{j : x_{j} \in U} Δ_{x_{j}} f (U \cap P_{j - 1}) \geq \sum_{j : x_{j} \in U} a_{j} .

Apply this to each

T_{i}

and interchange the finite sums. Every element occurs exactly

k

i = 1 \sum t f (T_{i}) \geq j = 1 \sum n k a_{j} = k (f (T) - f (\emptyset)) = k f (T) .

a_{j}

can be negative: exact multiplicity, rather than merely at least

k

occurrences, is what makes the argument valid without monotonicity. In fact the nonnegative function hypothesis is unnecessary here. If

T = \emptyset

, every

T_{i}

is empty and both sides vanish.

There are no discussions about this article yet.

There are currently no matching articles.