  Finding the $r\times r$ submatrix of maximum volume of a matrix $A\in\mathbb
R^{n\times n}$ is an NP hard problem that arises in a variety of applications.
We propose a new greedy algorithm of cost $\mathcal O(n)$, for the case $A$
symmetric positive semidefinite (SPSD) and we discuss its extension to related
optimization problems such as the maximum ratio of volumes. In the second part
of the paper we prove that any SPSD matrix admits a cross approximation built
on a principal submatrix whose approximation error is bounded by $(r+1)$ times
the error of the best rank $r$ approximation in the nuclear norm. In the spirit
of recent work by Cortinovis and Kressner we derive some deterministic
algorithms which are capable to retrieve a quasi optimal cross approximation
with cost $\mathcal O(n^3)$.
