On the Initial Set of Constraints for Graph-Based Submodular Function Maximization

Abstract

A crucial problem in combinatorial optimization is the submodular function maximization (SFM), and in many cases it involves graphs on which the maximization is specified. The problem is well-studied and hence there are several proposed algorithms in the literature. The greedy strategy quickly finds a feasible solution that guarantees an approximation of (1-1/e). However, there are many applications that expect an optimal result within a reasonable computational time. One popular method for finding the global optimum is the constraint generation (CG) algorithm. Traditionally, the initial feasible solution of CG is given by the greedy algorithm. It turns out that choosing different starting point than the greedy solution might lead to better performance in terms of running time. In this paper we introduce such a strategy which is beneficial on non-complete bipartite graphs. Benchmarking results on different versions of the solution methods are shown to demonstrate the efficiency of the proposed methods.