On dominated \(\ell_1\) metrics (Q5939287): Difference between revisions

A class \(\ell^{\text{dom}}_1(p)\) of \(\ell_1\)-embeddable metrics corresponding to a given metric \(p\) are studied. This class is defined as the set of all convex combinations of \(p\)-dominated line metrics. The main result is that the gap between the distortions of embedding of a finite metric \(p\) of size \(n\) into \(\ell_2\) versus into \(\ell^{\text{dom}}_1(p)\) is at most \(O(\sqrt{\log n})\), and this bound is essentially tight.