当前位置:

首页 > 业界资讯 > 无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

谷歌博客放出新研究,求解无向图的最小割问题。1996年,美国计算机科学家DavidRKarger连同其他研究者在论文《Anewapproachtotheminimumcutproblem》中提出了一个令人惊讶的随机算法Karger算法,其在理论计算机科学中非常重要,尤其适用于大规模图的近似最小割问题。Karger算法可以在时间为O(mlog^3n)的图中找到一个最小割点,他们将这个时间称之为近线性时间,意思是线性乘以一个多对数因子。在谷歌刚刚更新的一篇博客中,他们介绍了之前发布的一篇论文《Determin

本文目录
    谷歌博客放出新研究,求解无向图的最小割问题。

    1996 年, 美国计算机科学家 David R Karger 连同其他研究者在论文《 A new approach to the minimum cut problem》中提出了一个令人惊讶的随机算法 Karger 算法,其在理论计算机科学中非常重要,尤其适用于大规模图的近似最小割问题。

    Karger 算法可以在时间为 O (m log^3n) 的图中找到一个最小割点,他们将这个时间称之为近线性时间,意思是线性乘以一个多对数因子。

    在谷歌刚刚更新的一篇博客中,他们介绍了之前发布的一篇论文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》,研究获得了 ACM-SIAM SODA24 最佳论文奖。文章详细阐述了一个几乎是线性时间内(而不是近线性时间)运行的新算法,这个算法是确定性的,能够可靠地找到正确的最小割,改进了之前可能无法保证结果正确或只适用于简单图的算法。可以说这是自 Karger 著名的随机化算法以来的重大发现。
    无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
    • 论文地址:https://arxiv.org/pdf/2401.05627.pdf
    • 论文标题:Deterministic Near-Linear Time Minimum Cut in Weighted Graphs

    注:最小割问题(通常称为最小割)是关于图连通性的基本结构问题,它一般关注的是断开网络最简单的方法是什么?在图论中,去掉其中所有边能使一张网络流图不再连通(即分成两个子图)的边集称为图的割,一张图上最小的割称为最小割。
    无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
                                   一张图及其两个割:红色点线标出了一个包含三条边的割,绿色划线则表示了这张图的一个最小割(包含两条边)。

    方法介绍

    关于最小割问题,Karger 在 1996 年开创性的给出了一个近乎线性的时间随机算法,该算法能够以较高的概率找到最小割,并且该工作还给出了一个关键见解,即存在一个更小的图,它在很大程度上保留了所有割的大小。

    这个发现是很有用的,因为可以使用较小的图作为输入来运行较慢的算法,并且较慢的运行时间(就较小的图的大小而言)仍然可以与原始(较大)图的大小接近线性。

    事实上,关于最小割问题的许多结构发现都是沿着这个方向进行的。

    谷歌是这样做的,从具有 n 个节点的图 G 开始,然后依据论文《 Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs 》(作者为 Benzur、Karger)提出的割保留稀疏化方法,证明了可以构造一个边数更少的稀疏加权图 G',且在这个图上,几乎所有割的大小与原图 G 中相应割的大小大致相同。

    这个概念可以通过以下例子来说明:原始图由两个通过单一边连接的完全图组成,而稀疏化后的图边数更少,但边的权重更大,同时所有割的大小大致得以保留。

    无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

    为了构建这种较稀疏的图,Benzur 和 Karger 采用了独立采样边的方法。在这种方法中,图 G 中的每条边都有一定概率被包含在图 G' 中,并且其在 G' 中的权重会根据采样概率的倒数进行放大(例如,如果一条原权重为 1 的边以 10% 的概率被包含,则其权重调整为 10)。结果表明,这种非常简单(几乎是线性时间)的方法具有很高的成功概率,可以构建出保持割的图稀疏化。

    然而,Karger 算法是一种蒙特卡洛算法,即输出可能小概率不正确,并且除了与实际已知的最小割进行比较之外,没有已知的方法可以判断输出是否正确。

    因此,研究人员一直在努力探索解决近线性时间确定性算法开放问题的方法。由于 cut-preserving 图稀疏化的构造是 Karger 算法中唯一随机的组成部分,因此一种方法是在近线性时间内找到稀疏化的确定性构造(也称为去随机化)。

    2015 年,Kawarabayashi 和 Thorup 实现了一个重要的里程碑 —— 找到针对简单图(即每对节点之间至多有一条边且所有边权重等于 1 的图)的确定性近线性时间算法。

    该研究得出一个关键思路,即最小割和另一个重要的图结构(称为「low-conductance cut」)之间存在一些联系。这种联系对于后来在一般边权重图上去随机化 Karger 算法至关重要,并帮助谷歌得出了新算法。

    最小割和 low-conductance cut 的对齐

    图割 S 的 conductance 定义为 S 的 cut 大小与 S 的 volume 之比(假设 S 是切口的较小体积侧且非空),其中 S 的 volume 是 S 中节点的度数。

    low-conductance 的 cut S 直观地捕获了网络中的瓶颈,因为只有少量边(相对于其 volume)将 S 连接到图的其余部分。图的 conductance 被定义为图中任何 cut 的最小 conductance,并且大 conductance 的图(也称为扩展图)被认为是良好连接的,因为内部没有瓶颈。
    无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖
                                  红色虚线表示 cut 大小为 2,较小的一侧(底部)volume 为 24,因此其 conductance 为 1/12,这也是图的 conductance。

    Kawayabarashi 和 Thorup 观察到,在最小节点度数较大的简单图中,任何非平凡(即两侧至少有两个节点)最小割都必须具有 low conductance。根据这一观察,如果可以将图划分为连接良好的簇(cluster),则划分必须与每个非平凡最小割一致,因为每个簇必须完全位于每个 cut 的一侧。然后,将每个簇收缩为一个节点,并处理较小的图,其中原始图的所有非平凡最小割都完好无损。

    然而,对于加权图,上述观察不再成立,并且简单图情况中使用的相同划分可能与非平凡最小割不完全一致。

    如下图所示,Jason Li 2021 年观察到,这种划分仍然与非平凡最小割大致一致。特别地,对于非平凡最小割 S,存在与 S 相差不大的 cut S',使得 S' 与簇一致。Jason Li 进一步观察到,可以利用划分的这种特性来有效地去随机化 cut-preserving 图稀疏化的构造。

    无向图最小割问题取得新突破,谷歌研究获SODA 2024最佳论文奖

    谷歌设计的新算法旨在构建一种划分,来制定最小割的用例。与 Jason Li 在之前的工作中使用的更通用的现成方法相比,谷歌的这项研究更加精确、更加快捷。新研究在保证精度的同时在运行时间上也进行了优化,最终实现了针对最小割问题的近线性时间确定性算法。

    参考链接:https://research.google/blog/solving-the-minimum-cut-problem-for-undirected-graphs/
    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    业界资讯 谷歌
    相关文章 更多
    谷歌浏览器网页快捷方式怎么创建?Chrome发送到桌面【指南】_果粉控
    谷歌浏览器网页快捷方式怎么创建?Chrome发送到桌面【指南】_果粉控

    通过Chrome内置功能创建网页快捷方式 想要把常用网站变成桌面一键直达的入口?Chrome浏览器内置的快捷方式创建功能就能轻松实现。无论是生成独立应用窗口,还是传统桌面图标,下面这四种方法总有一款适合你。 一、通过地址栏创建桌面快捷方式 这个方法最实用——它能生成一个独立的桌面图标,双击后直接以应

    Chrome官方网页版入口
    Chrome官方网页版入口

    Chrome官方网页版入口:全方位解析谷歌浏览器的核心体验 很多朋友都在问,Chrome官方网页版的入口到底在哪里?答案其实很明确:https://www.google.com/chrome/。这个地址就是通往谷歌浏览器官网在线版的唯一官方大门。接下来,我们不妨深入看看,这个看似简单的页面背后,究竟

    苹果15plus怎么传照片到电脑 苹果15plus传照片到电脑方法
    苹果15plus怎么传照片到电脑 苹果15plus传照片到电脑方法

    手机早已成为中青年人的标配,不同年龄段对手机的需求其实差别不小。iPhone 15 Plus 作为当前热度颇高的机型,功能与服务覆盖得相当全面,能满足各类用户的需求。不过,有个实用问题很多人都会遇到——怎么把照片传到电脑上?今天就把两种主流方法掰开揉碎讲清楚,看完你就知道该怎么操作了。 方法一:数据

    谷歌亲儿子优先升级!安卓17正式版推送:21款设备首发尝鲜
    谷歌亲儿子优先升级!安卓17正式版推送:21款设备首发尝鲜

    谷歌正式推送安卓17系统,首批覆盖Pixel6至10系列共21款机型。新功能包括长按应用气泡菜单、应用内存限制机制、精确/大致定位权限选择,以及遗失设备追踪的FindHub功能,进一步优化隐私与设备管理体验。

    小米 MIUI不再支持自行安装谷歌GMS服务
    小米 MIUI不再支持自行安装谷歌GMS服务

    这几天,一些MIUI用户发现手机装不上谷歌GMS(谷歌移动服务)了。这事儿怎么说呢?小米社区里,多位认证为解答组的人员给出了统一回复:国内版MIUI出于合规原因,没有预置Google服务框架的机型,以后不再支持用户自己安装GMS服务。解答组还贴心地补了一句——如果真要用,可以去酷安搜相关教程。 受影

    等了7年!Edge终于支持谷歌账号登录同步数据
    等了7年!Edge终于支持谷歌账号登录同步数据

    微软Edge浏览器计划于2026年7月直接支持谷歌账号登录,用户无需微软账号即可跨设备同步浏览器数据。此举为偏好Edge但不想使用微软账号的用户提供原生单点登录体验,无需再走间接路径。

    小米MIXFold3如何安装谷歌 小米MIXFold3安装谷歌方法
    小米MIXFold3如何安装谷歌 小米MIXFold3安装谷歌方法

    小米MIXFold3未预装谷歌服务,需手动安装:先下载谷歌服务框架并开启未知来源,再安装GooglePlay商店并登录账号。但设备不支持完整GMS,部分应用可能有兼容性问题。

    安卓手机忘记解锁密码怎么办?3招教你打开手机
    安卓手机忘记解锁密码怎么办?3招教你打开手机

    安卓手机忘记密码时,可通过三种方式解锁:一、开启USB调试后,用ADB命令删除密码文件;二、连续错误输入五次,利用绑定的谷歌账号重置;三、使用刷机软件清除锁屏密码。

    提升流畅度:谷歌安卓17给App内存占用套上“紧箍咒”
    提升流畅度:谷歌安卓17给App内存占用套上“紧箍咒”

    安卓17引入四项重要安全改进:包括主动终止内存异常应用、新增本地网络权限防止设备扫描、强制动态加载库只读防止恶意注入、默认启用证书透明度防止伪造证书,全面提升系统安全。

    接连两位大咖出走,谷歌到底出了什么BUG?
    接连两位大咖出走,谷歌到底出了什么BUG?

    不到一周内,谷歌两位核心人物诺姆·沙泽尔与约翰·江珀相继离职。谷歌在AIAgent领域明显落后,产品线混乱,Antigravity2.0表现差强人意。尽管评测分数领先,但任务交付能力不足,组织架构的割裂是根本原因。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。