  The problem of maximizing a non-negative submodular function was introduced
by Feige, Mirrokni, and Vondrak [FOCS'07] who provided a deterministic
local-search based algorithm that guarantees an approximation ratio of $\frac 1
3$, as well as a randomized $\frac 2 5$-approximation algorithm. An extensive
line of research followed and various algorithms with improving approximation
ratios were developed, all of them are randomized. Finally, Buchbinder et al.
[FOCS'12] presented a randomized $\frac 1 2$-approximation algorithm, which is
the best possible.
  This paper gives the first deterministic algorithm for maximizing a
non-negative submodular function that achieves an approximation ratio better
than $\frac 1 3$. The approximation ratio of our algorithm is $\frac 2 5$. Our
algorithm is based on recursive composition of solutions obtained by the local
search algorithm of Feige et al. We show that the $\frac 2 5$ approximation
ratio can be guaranteed when the recursion depth is $2$, and leave open the
question of whether the approximation ratio improves as the recursion depth
increases.
