Inapproximability for metric embeddings into R^d
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00100795" target="_blank" >RIV/00216208:11320/08:00100795 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Inapproximability for metric embeddings into R^d
Original language description
(This paper is an extended abstract) We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into R^d, where d is fixed (and small). For d=1, it was known that approximating the minimum distortion with a factor better than roughly n^{1/12} is NP-hard. From this result we derive inapproximability with factor roughly n^{1/(22d-10)} for every fixed d. The proof involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala). For d at least 3, we obtain a stronger inapproximability result by a different reduction: one cannot efficiently distinguish between spaces embeddable in R^d with constant distortion from spaces requiring distortion at least n^{c/d}.
Czech name
Neaproximovatelnost pro vnoření do R^d
Czech description
(Tento článek je rozšířený abstrakt) Uvažujeme výpočetní problém - nalézt vnoření daného n-bodového metrického prostoru do R^d s nejmenší možnou distorzí, kde d je malá konstanta. Pro d=1 se vědělo, že distorzi nejde aproximovat s faktorem lepším než zhruba n^{1/12}. Z toho odvodíme neaproximovatelnost pro každé d s faktorem zhruba n^{1/(22d-10)}. Důkaz zahrnuje netriviální výsledek z geometrické topologii, jehož důkaz používá myšlenek J. Vaisaly. Pro dimenzi 3 a větší ukážeme silnější výsledek jinou redukcí: nelze efektivně odlišit prostory, které se dají vnořit do R^d s konstantní distorzí, od prostorů vyžadujících distorzi aspoň n^{c/d}.
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proc. 49th Annual IEEE Symposium on Foundations of Computer Science
ISBN
978-0-7695-3436-7
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
—
Publisher name
IEEE Computer Society
Place of publication
Los Alamitos, Calif.
Event location
Los Alamitos, Calif.
Event date
Jan 1, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000262484800042