...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Israel Journal of Mathematics >Metric extension operators, vertex sparsifiers and Lipschitz extendability
【24h】

Metric extension operators, vertex sparsifiers and Lipschitz extendability

机译：公制扩展运算符，顶点稀疏器和Lipschitz可扩展性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k/ log log k) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log(2) k/ log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomialtime algorithm for finding optimal operators.
机译：我们研究了Moitra（2009）以及Leighton和Moitra（2010）最近引入的顶点切割和流稀疏器。我们改进并概括了他们的结果。我们给出了一种新的多项式时间算法，用于构造O（log k / log log k）割流稀疏器，匹配稀疏器质量上最著名的存在上界，并改进O（log（ 2）k /日志log k）。我们表明，可以从近似最小度量扩展的线性算子获得流稀疏器。我们介绍了（线性）度量扩展算符的概念，证明了它们的存在，并给出了用于寻找最优算子的精确多项式时间算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号