Abstrakt
Zabýváme se problémem výpočtu nejmenší možné distorze pro vnoření daného n-bodového metrického prostoru do $\R^d$, kde d je pevně dané (a malé). Pro d=1 je známo, že aproximace minimální distorze s faktorem lepším než zhruba n^{1/12} je NP-těžká.