研究人员驳斥了人们对在线算法的普遍看法广达杂志

在生活中，我们有时不得不在没有我们想要的所有信息的情况下做出决定； 在计算机科学领域也是如此。 这是在线算法的领域——尽管它的名字如此，但并不一定涉及互联网。 相反，这些是解决问题的策略，在数据到达时做出响应，而不知道接下来会发生什么。 这种应对不确定性的能力使得这些算法对于解决现实世界的难题非常有用，例如管理笔记本电脑上的内存或选择向浏览网络的人显示哪些广告。

研究人员研究这些问题的广义版本，以研究解决这些问题的新方法。 其中最著名的是“k-服务器问题”，它描述了派遣一组代理来满足一个接一个的请求的棘手任务。 他们可能是维修技术人员或消防员，甚至是流动的冰淇淋销售员。

“定义这个问题非常简单，”说 马尔辛·比恩科斯基，波兰弗罗茨瓦夫大学的算法研究员。 但事实证明这“异常困难”。 自从研究人员开始攻击 k-1980 世纪 XNUMX 年代末的服务器问题，他们想知道在线算法到底能在多大程度上处理该任务。

几十年来，研究人员开始相信，总能达到一定水平的算法性能 k- 服务器问题。 因此，无论您正在处理什么版本的问题，都会有一种算法可以实现这一目标。 但在去年 XNUMX 月首次在线发表的一篇论文中，三位计算机科学家 显示 这并不总是可以实现的。 在某些情况下，每种算法都存在不足。

“我很高兴地说这对我来说是一个很大的惊喜，”说 阿努帕姆·古普塔（Anupam Gupta）在卡内基梅隆大学研究算法，并未参与该论文。 这项工作“更深入地洞察了该领域的核心问题”。

首先是计算机科学家 概述了这个问题 1988 年。为了了解这一点，让我们想象一家雇用水管工的公司。 当接到电话时，公司需要决定哪个水管工去哪个地点。 公司的目标——以及算法的目标 k- 服务器问题 - 是最小化所有管道工行驶的总距离。

棘手的是，公司事先并不知道电话来自哪里。 如果确实如此，那么它可以依赖一种了解未来的“离线算法”。 特别是，它可以使用理想的调度策略，为任何呼叫串找到总行程最少的解决方案。 没有任何在线算法可以击败它，甚至可以可靠地匹配它。

但研究人员希望尽可能接近。 他们通过比较每个策略中的行驶距离，计算所谓的竞争比来衡量在线算法的性能。 算法设计者试图制定接近离线理想的在线策略，将这个比率降低到 1。

假设我们的管道公司只有两名管道工，并且只为一条长街道提供服务。 电话一次接一个。 一种合理的第一种方法（称为贪婪算法）是调度距离每个来电位置最近的水管工。 但在这种情况下，该算法会遇到困难：想象一下，一名水管工从街道西端开始，另一名水管工从东端开始，所有呼叫都来自西端的两栋相邻房屋。 在这种情况下，一名水管工永远不会移动，而另一名水管工则在这两栋房子里辛苦工作。 回想起来，最好的策略是将两名水管工转移到容易出现问题的区域——但是，唉，你不可能知道那会在哪里。

即便如此，Bieńkowski 表示，还是有可能比贪心算法做得更好。 这 ”双重报道”算法以相同的速度将两个管道工移动到他们之间的任何呼叫，直到其中一个到达为止。 该方法比贪心算法获得了较低的竞争比。

虽然这个抽象问题与真正的管道公司无关，“ k-服务器问题本身确实是在线计算中的决定性问题，” 尤瓦尔·拉巴尼是耶路撒冷希伯来大学的计算机科学家，他是最近这篇论文的合著者。 在某种程度上，这是因为在工作期间开发的工具和技术 k- 服务器问题经常在在线算法研究的其他地方找到应用，甚至在它之外。

“这是算法研究的魔力之一，”他说。

当科学家研究这些问题时，他们喜欢将它们想象成与对手的游戏。 攻击者选择一系列邪恶的请求，使在线算法的性能与离线算法相比尽可能糟糕。 为了剥夺对手的部分权力，研究人员使用的算法包括： 随机决定.

这种策略相当有效，研究人员自 1990 世纪 XNUMX 年代初起就怀疑，总能找到一种随机算法来达到特定的性能目标：竞争比与 log 成正比 k，其中 k 是代理的数量。 这称为随机 k-服务器猜想，研究人员已经证明，对于某些空间或特定的点集合（相当于需要水管工的房屋）来说这是正确的。 但尚未在所有情况下得到证明。

和大多数研究人员一样，拉巴尼和他的合著者—— 塞巴斯蒂安·布贝克（SébastienBubeck） 微软研究院和 克里斯蒂安·科斯特 牛津大学的教授认为这个猜想是正确的。 “我没有理由怀疑这一点，”科斯特说。

但随着他们解决另一个在线问题，情况开始发生变化。 它与 k- 服务器问题，已知的竞争比下限出乎意料的高。 这让他们认为目标可能低至 log k 等加工。为 k- 服务器问题过于乐观。

拉巴尼说，是科斯特首先建议随机化 k- 服务器推测可能是错误的。 “他一说，一切都说得通了。”

为了反驳这个猜想，作者扮演了对手，制造了一场完美风暴，阻止任何在线算法达到对数竞争比 k。 他们的策略分为两部分：他们构建了一系列复杂的、类似分形的空间，并设计了对任何可能的算法来说都困难的请求序列的分布。 在算法的第一步中，空间的结构意味着它必须在两条相同的路径之间进行选择，其中一条最终需要根据请求进行额外的旅行。 然后，作者使用一种称为递归的方法来构建将这些决策点相乘的空间，迫使算法陷入不良选项的泥沼并提高成本。

这些选择让拉巴尼想起了罗伯特·弗罗斯特的诗“未走的路，”其中一位旅行者思考着穿过黄色树林的两条可能的路径。 “我们只是递归地应用这首诗，”他开玩笑说。 “然后事情就变得非常糟糕。”

作者表明，在他们构建的空间中，随机算法永远无法实现比（log k)²，推动日志的通用目标 k 永远遥不可及。 他们驳斥了这个猜想。

这部作品，荣获 最佳论文奖 在 2023年计算理论研讨会古普塔说，这标志着一个“坚实的理论”里程碑。 这种结果有助于表明我们希望从我们的算法中获得什么样的性能。 然而，在实践中，算法设计者通常不会围绕最坏的情况进行规划，因为对手是无所不能的，而且对未来完全无知。 当算法被用来解决现实世界的问题时，它们通常会超出理论预期。

这篇论文还证明了用于其他问题的随机算法的截止点，也可能对该领域的未来工作产生影响。 古普塔说，结果清楚地“凸显了作者使用的技术的力量”。

拉巴尼说，也许这些未来的发现将像这次一样超出研究人员的预期。 “在这种情况下，犯错感觉真的很好。”

广达 正在进行一系列调查，以更好地为我们的观众服务。 就拿我们的 计算机科学读者调查 您将有机会免费赢取 广达 商品。