Research
On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions
arXiv:2101.01631v2 Announce Type: cross Abstract: We demonstrate that from an algorithm guaranteeing an approximation factor for the ratio of submodular (RS) optimization problem, we can build another
arXiv:2101.01631v2 Announce Type: cross Abstract: We demonstrate that from an algorithm guaranteeing an approximation factor for the ratio of submodular (RS) optimization problem, we can build another algorithm having a different kind of approximation guarantee -- weaker than the classical one -- for the difference of submodular (DS) optimization problem, and vice versa. We also illustrate the link between these two problems by analyzing a extsc{Greedy} algorithm which approximately maximizes objective functions of the form Psi(f,g), where f,g are two non-negative, monotone, submodular functions and Psi is a {quasiconvex} 2-variables function, which is non decreasing with respect to the first variable. For the choice Psi(f,g)riangleq f/g, we recover RS, and for the choice Psi(f,g)riangleq f-g, we recover DS. To the best of our knowledge, this greedy approach is new for DS optimization. For RS optimization, it reduces to the standard extsc{GreedRatio} algorithm that has already been analyzed previously. However, our analysis is novel for this case.
Related
- Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
- An Approximation Algorithm for Graph Label Selection
Source: arXiv cs.LG | 2026-10-06