Finite Metric Embeddings: Good Algorithm?

Question

I have a finite metric space given as a (symmetric) k by k distance matrix. I would like an algorithm to (approximately) isometrically embed this in euclidean space R^(k-1). While it is not always possible to do exactly by solving the system of equations given by the distances I am looking for a solution that embeds with some (very small) controllable error.

I currently use multidimensional scaling (MDS) with the output dimension set to (k-1). It occurs to me that in general MDS may be optimized for the situation where you are trying to reduce the ambient embedding dimension to something less then (k-1) (typically 2 or 3) and that there may be a better algorithm for my restricted case.

Question: What is a good/fast algorithm for realizing a metric space of size k in R^{k-1} using euclidean distance?

Some parameters and pointers:

(1) My k's are relatively small. Say 3 < k < 25

(2) I don't actually care if I embed in R^{k-1}. If it simplifies things/makes things faster any R^N would also be fine as long as it's isometric. I'm happy if there's a faster algorithm or one with less error if I increase to R^k or R^(2k+1).

(3) If you can point to a python implementation I'll be even happier.

(4) Anything better then MDS would work.