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 f4cea1a..41452ad 100644 --- a/results.tex +++ b/results.tex @@ -272,6 +272,12 @@ By using standard concentration bounds, we can hope to obtain within $poly(n, \f \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 |