Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem (Q790044): Difference between revisions

A function Z on the power set \(2^ N\) of a finite set N is called nondecreasing, if Z(S)\(\leq Z(T)\) for all \(S\subset T\subset N\), and submodular, if \(\rho_ j(S)\geq \rho_ j(T)\) for all \(j\in N\backslash T\) and \(S\subset T\subset N\), where \(\rho_ j(S)=Z(S\cup \{j\})-Z(S)\) is the discrete derivative at \(S\subset N\) in direction \(j\in N\). The total curvature of a nondecreasing, submodular set function is the value \[ \alpha =\max_{j\in N^*}\{\frac{\rho_ j(\emptyset)-\rho_ j(N\backslash \{j\})}{\rho_ j(\emptyset)}\}, \] where \(N^*=\{j\in N:\rho_ j(\emptyset)>0\}\). Now let (N,X) be a matroid and Z a nondecreasing, submodular set function on \(2^ N\) satisfying \(Z(\emptyset)=0\). Then for the problem (*) ma\(x\{\) Z(S):\(S\in X\}\) the greedy algorithm is shown to find a solution with value at least \(1/(1+\alpha)\) times the optimum value, where this bound is best possible. If \(S^ 0=\emptyset \subset S^ 1\subset...\subset S^ k\) (the greedy solution) are the sets which are successively constructed by the greedy algorithm, the greedy curvature of Z is the value \[ \alpha_ G=\max_{o\leq i\leq k-1}\max_{j\in N^ i}\{\frac{\rho_ j(\emptyset)- \rho_ j(S^ i)}{\rho_ j(\emptyset)}\}, \] where \(N^ i=N^{^*}\cap \{j\in N\backslash S^ i: S^ i\cup \{j\}\in X\}\). It is shown that under the same assumptions as above the greedy algorithm produces a solution with a value at least \((1-\alpha_ G)\) times the optimum value of (*). Another bound in terms of the rank and the girth of X is given, which generalizes the bounds (e-1)/e for uniform matroids and 1/2 for general matroids. Finally, two tight bounds for the case that (N,X) is a general independence system are given, where the first is \((1- (1-\alpha /K)^ k)/\alpha\), where K and k are the sizes of a largest resp. smallest maximal indepndent set in X, and the second one is \(1/(p+\alpha)\), p being the minimum number of matroids that must be intersected to obtain X.