Dimensionality reduction with slack?
The standard reference for such a positive result is Piotr Indyk's paper on stable distributions:

http://people.csail.mit.edu/indyk/st-fin.ps

He shows a dimension reduction technique for $\ell_1$ where the distance between any pair of points does not increase (by more than factor $1+\epsilon$) with constant probability and distances do not decrease (by more than factor $1-\epsilon$) with high probability. The dimension of the embedding will be exponential in $1/\epsilon$.

There are probably follow up works that I'm not aware of.