Optimization with uniform size queries (Q527424)

Let \(f\) be a nonnegative, monotone, submodular set function over an \(n\)-element set \(U\). A \textit{value query} to \(f\) is a set \(S \subseteq U\) and its \textit{reply} is the value \(f(S)\). The authors study the following computational problem: given a positive integer \(k\) and \(f\) as above which can only be accessed using value queries of size \(k\), output a set \(S \subseteq U\) of size \(k\) that maximizes \(f(S)\). The authors show that polynomially many such queries are sufficient to obtain an approximation ratio of 1/2, and that an approximation ratio of \((1+\varepsilon)/2\) requires a number of queries that is exponential in \(\varepsilon k\). For the special case of \textit{coverage functions}, it is shown that an approximation ratio strictly better than 1/2 is attainable with polynomially many queries of size \(k\).