On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions
The paper investigates two optimization problems: maximizing a ratio of submodular functions (RS) and maximizing a difference of submodular functions (DS). It proves these problems are equivalent in terms of approximability under weaker conditions. This means an algorithm that approximates one problem can be transformed into an algorithm for the other, providing a unified framework for analyzing both types of optimization.