17 Retention under a budget
On this page · Permalink · Source line 1680
An archive cannot retain every object at full resolution. The first mathematically controlled retention problem is to choose a finite supplement that preserves as much future reach as possible.
Let \(C\subseteq W\) be the candidate nodes that may be retained and let \(M\) be a mandatory base set. For \(S\subseteq C\), define
The bridge graph remains fixed: retention changes the starting set, not the available intermediate vertices or edges. Deleting unretained intermediate vertices would define a different objective, for which the coverage proof below need not apply.
Theorem 17.1: Bridge coverage is monotone and submodular
The future reach utility \(U_M\) is a nonnegative monotone submodular set function on \(C\).
Proof
For each candidate \(x\in C\), let \(R_x\subseteq F\) be the set of future targets reachable from \(M\cup\{x\}\). Let \(R_M\) be the targets already reachable from \(M\). Reachability from a union of starting nodes is the union of their individual reach sets, so
Adding a candidate cannot remove a reachable target, so \(U_M\) is monotone.
Now let \(S\subseteq T\subseteq C\) and let \(x\in C\setminus T\). The marginal gain of adding \(x\) is the total weight of targets in \(R_x\) that are not already covered. Since \(T\) covers at least every target covered by \(S\), the set newly covered from \(T\) is contained in the set newly covered from \(S\). Therefore
which is submodularity.
Theorem 17.2: Greedy cardinality guarantee
Let \(k\) be an integer with \(1\leq k\leq|C|\). Starting from the empty supplement, let \(S_k\) result from repeatedly adding an unselected candidate with largest marginal future reach. Let \(O_k\) be an optimal supplement of size at most \(k\). Then
and therefore the greedy gain is at least \((1-1/e)\) times the optimal gain.
Proof
Write \(G_i=U_M(S_i)-U_M(\varnothing)\) and \(G^*=U_M(O_k)-U_M(\varnothing)\). By monotonicity and submodularity, the total marginal contribution of the at most \(k\) elements of \(O_k\) beyond \(S_i\) is at least \(G^*-G_i\). Hence at least one candidate has marginal gain at least \((G^*-G_i)/k\). Greedy chooses a candidate with at least that gain, so
Iterating from \(G_0=0\) gives
Rearranging gives the first bound. The inequality \((1-1/k)^k\le e^{-1}\) gives the second.
Warning 17.3: Arbitrary costs
For \(k=0\), both gains are zero without using the displayed division by \(k\). For a budget at least \(|C|\), retaining all candidates is optimal. The displayed theorem is the cardinality form of the standard submodular greedy bound [8]. A gain-per-cost rule for unequal costs is a different algorithm and does not inherit this guarantee. Zero-cost candidates also need an explicit convention.
