A note on maximizing the difference between a monotone submodular function and a linear function
share
Motivated by team formation applications, we study discrete optimization problems of the form max_S∈S(f(S)-w(S)), where f:2^V→R_+ is a non-negative monotone submodular function, w:2^V→R_+ is a non-negative linear function, and S⊆2^V. We give very simple and efficient algorithms for classical constraints, such as cardinality and matroid, that work in a variety of models, including the offline, online, and streaming. Our algorithms use a very simple scaling approach: we pick an absolute constant c≥1 and optimize the function f(S)-c· w(S) using a black-box application of standard algorithms, such as the classical Greedy algorithm and the single-threshold Greedy algorithm. These algorithms are based on recent works that use (time varying) scaling combined with classical algorithms such as the discrete and continuous Greedy algorithms (Feldman, WADS'19; Harshaw et al., ICML'19).
READ FULL TEXT