Overcoming the l1 non-embeddability barrier

摘要

A common approach for solving computational problems over a difficult metric space is to embed the 'hard' metric into L1 which admits efficient algorithms and is thus considered an 'easy' metric. This approach has proved successful or partially successful for important spaces such as the edit distance, but it also has inherent limitations: it is provably impossible to go below certain approximation for some metrics.