A Additional Experiments In this section, we present additional experiments which shed more light on the performance of X

Section 4.1, we consider =3 . In Section 4.2 and Appendix A.1, we examine the performance of different algorithms for the In Figure 5 the performance of both greedy heuristics is very similar under the two one-sided losses. We observe that the objective values are no longer uniformly positive, and are no longer monotonically increasing in the target size. In this section, we present the proofs of all theoretical results. The following lemma shows the submodularity of the objective U in the selection S . If (,M) is convex then U ( S) is submodular in S .