Nonmonotone Submodular Maximization Under Routing Constraints

In machine learning and big data, the optimization objectives based on set-cover, entropy, diversity, influence, feature selection, etc. are commonly modeled as submodular functions. Submodular (function) maximization is generally NP-hard, even in the absence of constraints. Recently, submodular maximization has been successfully investigated for the settings where the objective function is monotone or the constraint is computation-tractable. However, maximizing nonmonotone submodular function with complex constraints is not yet well-understood. In this paper, we consider the nonmonotone submodular maximization with a cost budget or feasibility constraint (particularly from route planning) that is generally NP-hard to evaluate. This is a very common issue in machine learning, big data, and robotics. This problem is NP-hard, and on top of that, its constraint evaluation is likewise NP-hard, which adds an additional layer of complexity. So far, few studies have been devoted to proposing effective solutions, leaving this problem currently unclear. In this paper, we first present an iterated greedy algorithm, which offers an approximate solution. Then we develop the proof machinery to demonstrate that our algorithm is a bicriterion approximation algorithm: it can accomplish a constant-factor approximation to the optimal algorithm, while keeping the over-budget tightly bounded. We also look at practical concerns for striking a balance between time complexity and over-budget. Finally, we conduct numeric experiments on two concrete examples to show our design’s efficacy in real-world scenarios.