Near Optimal Algorithms for Hard Submodular Programs with Discounted Cooperative Costs
This work provides incremental theoretical guarantees for machine learning applications like image matching and sensor placement, enabling more practical solutions to submodular problems.
The paper tackles hard submodular optimization problems, such as minimizing submodular costs under constraints, which typically have high hardness factors like Ω(√n), and achieves constant approximation factors by restricting cost functions to low-rank sums of concave over modular functions.
In this paper, we investigate a class of submodular problems which in general are very hard. These include minimizing a submodular cost function under combinatorial constraints, which include cuts, matchings, paths, etc., optimizing a submodular function under submodular cover and submodular knapsack constraints, and minimizing a ratio of submodular functions. All these problems appear in several real world problems but have hardness factors of $Ω(\sqrt{n})$ for general submodular cost functions. We show how we can achieve constant approximation factors when we restrict the cost functions to low rank sums of concave over modular functions. A wide variety of machine learning applications are very naturally modeled via this subclass of submodular functions. Our work therefore provides a tighter connection between theory and practice by enabling theoretically satisfying guarantees for a rich class of expressible, natural, and useful submodular cost models. We empirically demonstrate the utility of our models on real world problems of cooperative image matching and sensor placement with cooperative costs.