May, 2013

Bilu-Linial 稳定的最大割和最小多路割实例

PDF
TL;DR研究 Bilu 和 Linial 提出的稳定性概念，提出了一个基于半定编程的精确多项式算法解决具有 γ 稳定性的 Max Cut 问题，对于 γ <α_SC (n/2) 的情况，不存在可解决的凸松弛方法，此外还研究了最小多路径切问题的 4 - 稳定性。
stabilitymax cutsemidefinite programmingtractable convex relaxationweak stability
发现论文，激发创造
  • 一种超出最坏情况的图聚类的近线性时间逼近算法

    在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。

    Jun, 2024

  • 稳定的实例是否容易？

    这篇论文介绍了离散优化问题的稳定实例概念，并指出在许多实际情况下，只有足够稳定的实例才是有意义的。 然后就稳定的 NP - 困难问题是否更容易解决提出问题。特别地，是否存在算法可以正确且在多项式时间内解决某些 NP - 困难问题的所有足够稳定的实例。本文重点研究了最大割问题，并表明这确实是可能的。

    Jun, 2009

  • 最大割和最小特征值

    本研究提出了一种基于谱分割的近似算法，可以在多项式时间内解决 max cut 问题，并取得了高质量的结果。

    Jun, 2008

  • 基于稳定性扰动的中心聚类

    本文证明了当度量空间中没有 Steiner 点时，对于任何以中心为基础的聚类目标函数（例如 k - 中位数，k - 均值和 k - 中心），我们可以有效地找到最优的聚类，假设仅稳定于基础度量的 3 倍扰动，对于一般的度量，稳定性因子为 2 + 根号 3 扰动，我们还在相关条件下提出了 NP 困难性结果。

    Sep, 2010

  • 近似线性时间的最小割

    通过在最小割问题和最大生成树包裹之间使用半对偶关系，结合我们先前开发的随机采样技术，我们显着提高了解决无向图上最小割问题的已知时间界限，通过随机算法在 O (mlog^3n) 时间内高概率找到 m 边 n 顶点图中的最小割，并使用 O (n^2logn) 时间内高概率找到所有最小割。

    Dec, 1998

  • 通过 Grothendieck 不等式解同步和 MaxCut 问题的 SDP

    通过引入非凸约束形式并应用 Riemannian trust-region 方法，该论文研究了 MaxCut 和同步问题中的秩约束半定规划，并建立了一个 Grothendieck 型不等式证明局部最大值和危险鞍点都在离全局最大值一个小倍数距离的情况下，SDPs 可以在已知精度内得到解决。

    Mar, 2017

  • 分布式最小割近似

    本文通过分布式算法研究了在标准同步消息传递模型下，计算近似的最小边割问题，提出了随机分层技术作为分析随机边采样的一种简单方法，并给出了两个分布式算法的时间复杂度，同时还强化了上一篇研究的下界。

    May, 2013

  • 超模极大化 —— 非非负性保证、快速算法和应用

    本文研究次模函数的优化和算法问题，提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法，并通过实验设计对其进行了验证。

    Apr, 2019

  • 均匀稳定算法的高概率泛化界限，近乎最优速率

    本文提出了一种新的方法来证明算法稳定性，并且在此基础上给出了关于多次随机梯度下降和正则 ERM 的高概率泛化界，同时也解决了一些之前的开放性问题。

    Feb, 2019

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

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

    Aug, 2019