  We generalize the notion of the best separable approximation (BSA) and best
W-class approximation (BWA) to arbitrary pure state entanglement measures,
defining the best zero-$E$ approximation (BEA). We show that for any polynomial
entanglement measure $E$, any mixed state $\rho$ admits at least one
"$S$-decomposition," i.e., a decomposition in terms of a mixed state on which
$E$ is equal to zero, and a single additional pure state with (possibly)
non-zero $E$. We show that the BEA is not in general the optimal
$S$-decomposition from the point of view of bounding the entanglement of
$\rho$, and describe an algorithm to construct the entanglement-minimizing
$S$-decomposition for $\rho$ and place an upper bound on $E(\rho)$. When
applied to the three-tangle, the cost of the algorithm is linear in the rank
$d$ of the density matrix and has accuracy comparable to a steepest descent
algorithm whose cost scales as $d^8 \log d$. We compare the upper bound to a
lower bound algorithm given by Eltschka and Siewert for the three-tangle, and
find that on random rank-two three-qubit density matrices, the difference
between the upper and lower bounds is $0.14$ on average. We also find that the
three-tangle of random full-rank three qubit density matrices is less than
$0.023$ on average.
