(no subject)

[am]

E. Balkanski, A. Rubinstein,
Y. Singer (2018) "An Exponential
Speedup in Parallel Running Time
for Submodular Maximization without
Loss in Approximation."
About it. Earlier:
E. Balkanski, Y. Singer (2018)
"The adaptive complexity
of maximizing a submodular
function." In STOC, 2018.

G.L. Nemhauser, L.A. Wolsey (1978)
"Best algorithms for approximating
the maximum of a submodular set
function." Math. of oper. res.,
3(3):177-188.
G.L. Nemhauser, L.A. Wolsey,
M.L. Fisher (1978) "An analysis
of approximations for maximizing
submodular set functions."
Math. Progr., 14(1):265-294.

Update:
Recently it is proven that
classical computers can solve
the “recommendation problem”
nearly as fast as QC (on
average, for a fixed error
and fixed query size).
Ewin Tang (2018) "A quantum-
inspired classical algorithm
for recommendation systems."