ACM通信
ACM新闻
研究人员为网络流实现了“快得荒唐”的算法
目前，这主要是一个理论上的进步，因为速度的提高只在比我们在现实世界中遇到的网络大得多的网络中起作用，对于这种网络，最大流量问题已经可以相当快地解决(至少，i
信贷:2 dwork /上面
一组计算机科学家已经提出了一个大大加快算法这是计算机科学中最古老的问题之一:最大流量。这个问题问的是，如果网络中的链路有容量限制，有多少物质可以通过网络从一个源头流向一个目的地。
新算法“快得荒唐”，他说Daniel Spielman耶鲁大学的。“我实际上倾向于相信……解决这个问题这么好的算法是不存在的。”
自20世纪50年代以来，人们一直在研究最大流量，当时它被用来研究苏联铁路系统。“它可能比计算机科学的理论还要古老，”他说伊迪丝·科恩加州山景城谷歌研究中心。这个问题有很多应用:互联网数据流、航班调度，甚至将求职者与空缺职位匹配。新的论文处理了最大流量和更一般的问题，在这个问题中你也想要最小化成本。多年来，这两个问题激发了算法技术的许多最大进步。斯皮尔曼说:“这几乎就是为什么我们有一个算法领域。”
新算法在“几乎线性”的时间内解决了这两个问题，这意味着算法的运行时间与它最初仅仅写下网络细节所花的时间大致成正比。对于这些问题，没有其他算法能在所有可能的网络上运行得如此之快。结果让他“上蹿下跳”，他说Satish饶加州大学伯克利分校的教授。“这太棒了。”
从广达电脑杂志
查看全文
没有发现记录