  First, for the for the submodular $k$-secretary problem with shortlists [1],
we provide a near optimal $1-1/e-\epsilon$ approximation using shortlist of
size $O(k poly(1/\epsilon))$. In particular, we improve the size of shortlist
used in \cite{us} from $O(k 2^{poly(1/\epsilon)})$ to $O(k poly(1/\epsilon))$.
As a result, we provide a near optimal approximation algorithm for random-order
streaming of monotone submodular functions under cardinality constraints, using
memory $O(k poly(1/\epsilon))$. It exponentially improves the running time and
memory of \cite{us} in terms of $1/\epsilon$.
  Next we generalize the problem to matroid constraints, which we refer to as
submodular matroid secretary problem with shortlists. It is a variant of the
\textit{matroid secretary problem} \cite{feldman2014simple}, in which the
algorithm is allowed to have a shortlist. We design an algorithm that achieves
a $\frac{1}{2}(1-1/e^2 -\epsilon)$ competitive ratio for any constant
$\epsilon>0$, using a shortlist of size $O(k poly(\frac{1}{\epsilon}))$.
Moreover, we generalize our results to the case of $p$-matchoid constraints and
give a $\frac{1}{p+1}(1-1/e^{p+1}-\epsilon )$ approximation using shortlist of
size $O(k poly(\frac{1}{\epsilon}))$. It asymptotically approaches the best
known offline guarantee $\frac{1}{p+1}$ [22]. Furthermore, we show that our
algorithms can be implemented in the streaming setting using $O(k
poly(\frac{1}{\epsilon}))$ memory.
