Using Partial Monotonicity in Submodular Maximization
  Over the last two decades, submodular function maximization has been the
workhorse of many discrete optimization problems in machine learning
applications. Traditionally, the study of submodular functions was based on
binary function properties. However, such properties have an inherit weakness,
namely, if an algorithm assumes functions that have a particular property, then
it provides no guarantee for functions that violate this property, even when
the violation is very slight. Therefore, recent works began to consider
continuous versions of function properties. Probably the most significant among
these (so far) are the submodularity ratio and the curvature, which were
studied extensively together and separately.
  The monotonicity property of set functions plays a central role in submodular
maximization. Nevertheless, and despite all the above works, no continuous
version of this property has been suggested to date (as far as we know). This
is unfortunate since submoduar functions that are almost monotone often arise
in machine learning applications. In this work we fill this gap by defining the
monotonicity ratio, which is a continues version of the monotonicity property.
We then show that for many standard submodular maximization algorithms one can
prove new approximation guarantees that depend on the monotonicity ratio;
leading to improved approximation ratios for the common machine learning
applications of movie recommendation, quadratic programming and image
summarization.
