  In this work we give two new algorithms that use similar techniques for
(non-monotone) submodular function maximization subject to a cardinality
constraint.
  The first is an offline fixed parameter tractable algorithm that guarantees a
$0.539$-approximation for all non-negative submodular functions.
  The second algorithm works in the random-order streaming model. It guarantees
a $(1/2+c)$-approximation for symmetric functions, and we complement it by
showing that no space-efficient algorithm can beat $1/2$ for asymmetric
functions. To the best of our knowledge this is the first provable separation
between symmetric and asymmetric submodular function maximization.
