tlooto
Sign up
Computer ScienceMathematics

Approximate submodularity and its applications

DasAbhimanyu, KempeDavid

2018JOURNAL OF MACHINE LEARNING RESEARCH

tlooto Summary

The submodularity ratio is introduced as a measure of how "close" to submodular a set function f is and it is shown that when f has subModularity ratio γ, the greedy algorithm for maximizing f provides a submodality ratio of 1.

Abstract

We introduce the submodularity ratio as a measure of how "close" to submodular a set function f is. We show that when f has submodularity ratio γ, the greedy algorithm for maximizing f provides a (...

Citation format

DASABHIMANYU; KEMPEDAVID. Approximate submodularity and its applications. JOURNAL OF MACHINE LEARNING RESEARCH, 2018.