G-2003-27
Algorithms for l1-Embeddability and Related Problems
et référence BibTeX
Assouad has shown that a real-valued distance
d = (dij)
1 ≤ i < j ≤ n
is isometrically embeddable in l1-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 l1-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 l1-embeddable by another one which is are also studied.
Paru en mai 2003 , 30 pages
Ce cahier a été révisé en janvier 2007