Algorithms for Optimizing the Ratio of Monotone K-Submodular Functions

Abstract

We study a new optimization problem that minimizes the ratio of two monotone k -submodular functions. The problem has applications in sensor placement, influence maximization, and feature selection among many others where one wishes to make a tradeoff between two objectives, measured as a ratio of two functions (e.g., solution cost vs. quality). We develop three greedy based algorithms for the problem, with approximation ratios that depend on the curvatures and/or the values of the functions. We apply our algorithms to a sensor placement problem where one aims to install k types of sensors, while minimizing the ratio between cost and uncertainty of sensor measurements, as well as to an influence maximization problem where one seeks to advertise k products to minimize the ratio between advertisement cost and expected number of influenced users. Our experimental results demonstrate the effectiveness of minimizing the respective ratios and the runtime efficiency of our algorithms. Finally, we discuss various extensions of our problems.