Algorithms for ℓ1-Embeddability and Related Problems

Assouad has shown that a real-valued distance d = (d_ij)_{1 ≤ i < j ≤ n} is isometrically embeddable in ℓ₁space if and only if it belongs to the cut cone on n points. Determining if this condition holds is NP-complete. We use Assouad's result in a constructive column generation algorithm for ℓ₁-embeddability. The subproblem is an unconstrained 0-1 quadratic program, solved by Tabu Search and Variable Neighborhood Search heuristics as well as by an exact enumerative algorithm. Computational results are reported. Several ways to approximate a distance which is not ℓ₁-embeddable by another one which is are also studied.