• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
【24h】

Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

机译：高特征值最小线性排列问题的逼近保证。

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

摘要

Given an undirected graph G = (V, E) and positive edge weights {w_e}_(e∈E), a linear arrangement is a permutation π : V → [n]. The value of the arrangement is val(G, π) := 1 Σ_(e={u,v}) w_e|π(u)-π(v)|. In the minimum linear arrangement problem (MLA), the goal is to find a linear arrangement π~* that achieves val(G,π~*) = MLA(G) := min_π val(G, π). In this paper, we show that for any ∈ > 0 and positive integer r, there is an O(n~(r/∈))-time randomized algorithm which, given a graph G, returns a permutation π such that val(G,π)≤(1+2/(1-∈)λ_(r+1)(L)) MLA(G)+O(log n~(1/2)Σ_(e∈E)w_e) with high probability. Here L is the normalized Laplacian of G and λ_r(L) is the r-th eigenvalue of L Our algorithm gives a constant factor approximation for regular graphs that are weak expanders.
机译：给定无向图G =（V，E）和正边权重{w_e} _（e∈E），线性排列是置换π：V→[n]。排列的值为val（G，π）：= 1 / nΣ_（e = {u，v}）w_e |π（u）-π（v）|。在最小线性排列问题（MLA）中，目标是找到一个线性排列π〜*，使其达到val（G，π〜*）= MLA（G）：=min_πval（G，π）。在本文中，我们表明对于任何∈> 0和正整数r的情况，都有O（n〜（r /∈））时间随机算法，给定图G，它返回置换π，从而val（G ，π）≤（1 + 2 /（1-ε）λ_（r + 1）（L））MLA（G）+ O（log n / n〜（1/2）Σ_（e∈E）w_e）其中高概率。这里L是G的规范化拉普拉斯算子，而λ_r（L）是L的第r个特征值。对于弱扩张器的规则图，该算法给出了恒定因子近似值。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号