Appendix

Inparticular,these bounds are relative to the optimal algorithm with a budgetB, we denote its mutual informationasOPT(B). Our proof will convert this setting back tothe classic unweighted setting so we can invokethe standard (1 1/e)-result. By scaling this x,m value by 1/λm we can imagine splitting the effect of(x,m) into λm copies of itself, and considering each of these copies as unit-weight elements. By submodularity, all such items have diminishing returns and their contribution cannot increase. However,the unit weight copies of(x,m) are essentially independent, and so their x,m/λm score does not decrease(ifweaddallλm weincreasemutualinformation byatotalof x,m).