Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice

In this work, we focus on maximizing the ratio of two monotone DR-submodular functions on the integer lattice. It is neither submodular nor supermodular. We prove that the Threshold Decrease Algorithm is a 1 - e(-(1-kg)) - e approximation ratio algorithm. Additionally, we construct the relationship between maximizing the ratio of two monotone DR-submodular functions and maximizing the difference of two monotone DR-submodular functions on the integer lattice. Based on this relationship, we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone DR-submodular functions on the integer lattice and prove its approximation ratio is f (x)-g(x) ? 1-e(-(1-kg)) f (x*)-g(x*)- e. To the best of our knowledge, before us, there was no work to focus on maximizing the ratio of two monotone DR-submodular functions on integer lattice by using the Threshold Decrease Algorithm.