diff options
Diffstat (limited to 'results.tex')
| -rw-r--r-- | results.tex | 6 |
1 files changed, 6 insertions, 0 deletions
diff --git a/results.tex b/results.tex index 1848d35..c9acedd 100644 --- a/results.tex +++ b/results.tex @@ -314,6 +314,12 @@ learning $f$ approximately to optimize it. \subsection{Parametric submodular functions} +\textbf{Note:} all known examples of submodular functions are parametric. The +question is not parametric vs non-parametric but whether or not the number of +parameters is polynomial or exponential in $n$ (the size of the ground set). +For all examples I know except martroid rank functions, it seems to be +polynomial. + \subsubsection{Influence Functions} Let $G = (V, E)$ be a weighted directed graph. Without loss of generality, we |