平衡下的路由
介绍了一种新的方法来解决最大流问题,使用 alpha-congestion-approximators 在无向,容量图中,通过计算简单的函数,维护任意流来优化拥挤度,并提出使用类似 Spielman and Teng (STOC 2004)解决 Laplacian 系统问题的方法。
Apr, 2013
在半随机图模型中,我们研究了平衡切割问题的精确性和时间复杂度,并且提出了第一个近似线性时间算法,以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。
Jun, 2024
本文通过分布式算法研究了在标准同步消息传递模型下,计算近似的最小边割问题,提出了随机分层技术作为分析随机边采样的一种简单方法,并给出了两个分布式算法的时间复杂度,同时还强化了上一篇研究的下界。
May, 2013
通过访问顶点并返回起始位置的单一代理器的边权无向图探索,我们在 competitive ratio 上获得了 10/3 的改进下界,这与 Dobrev 的下限相比较,也适用于平面图。
Feb, 2020
该论文提出了一种新的框架来近似解决容量限制下的流问题,并将其应用于提供渐进更快的最大流问题和最大并发多商品流问题的算法,该算法优化了现有的时间复杂度,并给出了多个新的技术工具如非欧几里得梯度下降、流加密器以及近似线性的路由机制。
Apr, 2013
探究搜索者搜索未知的加权无向图的问题,证明最近邻算法的竞争比率在树中为 θ(logn),并研究参数范围内算法 Blocking 在单轮图上是 3-competitive,在仙人掌图上是 5/2+√2 约等于 3.91-competitive。
Apr, 2020
本论文提出了一种新的内点法来处理最大流问题,该算法通过将其应用于线性规划制定最大流、最小费用流和有损广义最小费用流的问题,并借鉴 Daitch 和 Spielman 的方法分析,最终在 O (m√nlogO (1)(U/ε)) 的时间内解决这些问题,同时在使用 Spielman 和 Peng 的 Laplacian 系统求解器进行并行化后,达到了 O (√nlogO (1)(U/ε)) 和 O (m√nlogO (1)(U/ε)) 的时间。
Dec, 2013
本文展示了在至少需要 ω(n^(2/(d+2))) 的节点度时(其中 d 为维度),可以从有向无权图中恢复欧几里得度量和相关密度的估计,其中我们的估计器基于有向图上的随机游走的特征化和相应连续极限。
Nov, 2014
该论文介绍了一种家族型的多路 Cheeger 常数,在有符号的图形中引入了一种度量双重性,以及用于找到近似平衡子图的谱聚类方法,并使用签署的拉普拉斯矩阵估计了极端特征值。
Nov, 2014