Apr, 2020

关于树、单圈图和仙人掌图的在线图探索

PDF
TL;DR探究搜索者搜索未知的加权无向图的问题，证明最近邻算法的竞争比率在树中为 θ(logn)，并研究参数范围内算法 Blocking 在单轮图上是 3-competitive，在仙人掌图上是 5/2+√2 约等于 3.91-competitive。
undirected weighted graphsearchernearest neighbor algorithmblockingcompetitive ratio
发现论文，激发创造
  • 图探索竞争问题的改进下界

    通过访问顶点并返回起始位置的单一代理器的边权无向图探索，我们在 competitive ratio 上获得了 10/3 的改进下界，这与 Dobrev 的下限相比较，也适用于平面图。

    Feb, 2020

  • CONGEST 模型二次和接近二次的下界

    该研究给出在 CONGEST 模型中自然图问题的第一个超线性下界，并回答了长期以来的一个开放性问题，特别地，证明任何精确计算最小顶点覆盖或最大独立集的算法都需要在最坏情况下花费 Ω(n²/log²n) 轮，这样强的下界不仅局限于 NP 困难问题。

    May, 2017

  • 有向无权图中的度量恢复

    本文展示了在至少需要 ω(n^(2/(d+2))) 的节点度时（其中 d 为维度），可以从有向无权图中恢复欧几里得度量和相关密度的估计，其中我们的估计器基于有向图上的随机游走的特征化和相应连续极限。

    Nov, 2014

  • 通过边界检测查询学习图

    这篇论文探讨了用边缘检测查询学习一般图的问题，研究并给出了 Las Vegas 算法和 Monte Carlo 算法不同的轮数和查询数量，概述了解决此问题的难点和限制。

    Mar, 2018

  • 图中的确定性和概率二分搜索

    本文研究在带权无向图中的二分查找问题，并给出了一个在查询顶点时几乎达到信息熵下界的算法，同时也探讨了该问题在不同情况下的复杂性。

    Mar, 2015

  • 基于学习的图搜索问题算法

    在这篇研究论文中，我们考虑了最近由 Banerjee 等人（2022）提出的预测图搜索问题。我们设计了一种算法来应对未知图上的搜索任务，并且在预测误差上提供了最优或接近最优的算法依赖关系的保证。此外，我们还提出了 Banerjee 等人（2022）算法在已知图上的性能边界，并为该情景建立了新的下界。

    Feb, 2024

  • 一种简单的近线性时间最小割算法

    该论文研究无向带权图中的最小割问题，并给出了一种用于寻找 2 - 保留（切断图 G 中两个边）图的生成树 T 的最小割的简单算法。该算法被运用在代替 Karger 的近线性时间最小割算法中的复杂子例程，采用自包含版本的 Karger 算法的新程序，其易于说明和实现。该程序在高概率下可以以 O（mlog3n）的时间复杂度下求出一个由 m 条边和 n 个点构成的图的最小割，与 Karger 的方法的复杂度相匹配。

    Aug, 2019

  • 通过随机 $2$-Out 缩减加速边连通性算法

    使用基于 2 出边采样的简单新的随机收缩方法解决全局最小割问题，进而获得更好的边连通性、分布式算法和并行计算等方面的表现。

    Sep, 2019

  • 竞赛方案的查询复杂度

    本文研究在仅查询尽可能少的边的情况下找到锦标赛的最佳顶点集合的问题，并给出了 Condorcet 非输家集合的计算方法，并证明了任何找到 Copeland 集合，Slater 集合，Markov 集合，双方集合，未覆盖集合，Banks 集合和顶点集合的算法在最坏情况下必须查询 Ω(n²) 条边，但如果输入的锦标赛的顶部循环的大小不超过 k，则可以只查询 O (nk + n log (n)/(log (1-1/k))) 条边即可找到所有锦标赛解。

    Nov, 2016

  • 利用低树宽计算所有对最短路径

    本论文提出了两种新的算法，用于计算带有实数边权（可能为负数）的有向图的全源最短路径。这两种算法运行时间复杂度为 O (n^2w_d)，可用于空间和时间推理，比 Floyd-Warshall 算法和 Johnson 算法更快，并且具有规划和调度社区的相关性。

    Jan, 2014