Scholarlink

<p>We study deterministic online embeddings of metric spaces into normed spaces and into trees against an adaptive adversary. Main results include a polynomial lower bound on the (multiplicative) distortion of embedding into Euclidean spaces, a tight exponential upper bound on embedding into the line, and a (1 + <i>ϵ</i>)-distortion embedding in <i>ℓ</i><sup>∞</sup> of a suitably high dimension.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Online embedding of metrics

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年2月17日

查看全文
  • Ilan Newman,
  • Yuri Rabinovich

摘要

We study deterministic online embeddings of metric spaces into normed spaces and into trees against an adaptive adversary. Main results include a polynomial lower bound on the (multiplicative) distortion of embedding into Euclidean spaces, a tight exponential upper bound on embedding into the line, and a (1 + ϵ)-distortion embedding in ℓ∞ of a suitably high dimension.