Poster
Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
Christopher Harshaw · Moran Feldman · Justin Ward · Amin Karbasi
Pacific Ballroom #139
Keywords: [ Combinatorial Optimization ]
[
Abstract
]
Abstract:
It is generally believed that submodular functions--and the more general class of
-weakly submodular functions--may only be optimized under the non-negativity assumption . In this paper, we show that once the function is expressed as the difference , where is monotone, non-negative, and -weakly submodular and is non-negative modular, then strong approximation guarantees may be obtained. We present an algorithm for maximizing under a -cardinality constraint which produces a random feasible set such that ,
whose running time is , independent of . We extend these results to the unconstrained setting by describing an algorithm with the same approximation guarantees and faster runtime. The main techniques underlying our algorithms are two-fold: the use of a surrogate objective which varies the relative importance between and throughout the algorithm, and a geometric sweep over possible values. Our algorithmic guarantees are complemented by a hardness result showing that no polynomial-time algorithm which accesses through a value oracle can do better. We empirically demonstrate the success of our algorithms by applying them to experimental design on the Boston Housing dataset and directed vertex cover on the Email EU dataset.
Live content is unavailable. Log in and register to view live content