AF: Small: Towards New Relaxations for Online Algorithms

AF：小：在线算法的新放松

• 批准号: 2224718
• 负责人: Anupam Gupta
• 金额: $ 60万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2224718&HistoricalAwards=false
• 关键词: AF; Small; Towards; New; Relaxations

We all are regularly asked to make decisions in the face of uncertainty: we decide how best to drive to work or how and at what prices to buy and sell things (everything from houses to groceries). And our computers make such choices as well to give good performance to their users: which order to process tasks q to maximize the throughput or minimize user delay, or which pages to keep in fast memory (because they will be accessed again soon) and which others moved to slower memory. These questions do not fall in the classical ``one-shot'' framework of computation, where an algorithm reads in the input, processes it and produces its output. Instead, they fall in the area of sequential decision-making, and specifically of online algorithms, which provides a framework in which we can formalize such questions and also reason about their solutions. For such problems, there is a natural tension between two competing desires: (a) to make decisions that maximize the instantaneous gratification but may be poor in the long run, or (b) to wait and maneuver into a good position to make gains in the future. This project aims to develop general-purpose algorithms that find optimal ways of hedging between these two extremes for a broad class of optimization problems in online optimization.As an example, consider the k-server problem, which is a central problem in this area. In this, one controls k servers which move between some locations in a metric space. A sequence of requests arrives over time, where each request specifies a location, and one must move one of the servers from its current position to this requested location. The goal is to minimize the total server movement. Given a request, which server should be moved? As mentioned above, there is a tradeoff between being greedy and moving the servers closest to the requested location and moving more distant servers to be in a better position for future requests. Developing good algorithms for this and related problems has been a major challenge in the area. This project will investigate three ways of addressing the challenge: (a) To develop general principles for designing broadly-applicable algorithms for randomized settings, and in particular, to extend the classical work function algorithm (which is near-optimal for the deterministic setting) to randomized settings; (b) To get extendable, robust convex relaxations for k-server and its generalizations, and to use these relaxations to obtain good algorithms; (c) To develop a broader framework for typical instances, instead of focusing on the worst-case instances. Our work will draw on ideas from linear and convex optimization, stochastic optimization and optimal stopping theory, and online learning in order to deepen our understanding of these and other central questions in optimization under uncertainty.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

我们所有人经常被要求在面对不确定性时做出决定：我们决定如何最好地开车去上班，或者如何以及以什么价格购买和出售东西（从房屋到杂货的一切）。我们的计算机也会做出这样的选择，以便为用户提供良好的性能：处理任务 q 的顺序以最大化吞吐量或最小化用户延迟，或者将哪些页面保留在快速内存中（因为它们很快就会被再次访问）以及哪些页面其他人则转向较慢的记忆。这些问题不属于经典的“一次性”计算框架，其中算法读取输入、处理它并产生输出。相反，它们属于顺序决策领域，特别是在线算法，它提供了一个框架，我们可以在其中形式化此类问题并推理其解决方案。对于此类问题，两种相互竞争的欲望之间存在着天然的紧张关系：（a）做出最大化瞬时满足感的决策，但从长远来看可能会很糟糕，或者（b）等待并操纵到一个有利的位置，以在未来的发展中获得收益。未来。该项目旨在开发通用算法，为在线优化中的一大类优化问题找到在这两个极端之间进行对冲的最佳方法。例如，考虑 k 服务器问题，这是该领域的核心问题。在这种情况下，一个人控制在度量空间中的某些位置之间移动的 k 个服务器。随着时间的推移，一系列请求到达，其中每个请求指定一个位置，并且必须将其中一个服务器从其当前位置移动到该请求的位置。目标是最大限度地减少服务器总移动量。给定一个请求，应该移动哪个服务器？如上所述，在贪婪和移动距离请求位置最近的服务器与移动更远的服务器以更好地处理未来请求之间存在权衡。针对此问题和相关问题开发良好的算法一直是该领域的主要挑战。该项目将研究解决这一挑战的三种方法： (a) 制定为随机设置设计广泛适用的算法的一般原则，特别是扩展经典功函数算法（对于确定性设置来说是近乎最佳的）随机设置； (b) 获得 k-server 及其泛化的可扩展、鲁棒的凸松弛，并使用这些松弛获得良好的算法； (c) 为典型情况制定更广泛的框架，而不是关注最坏情况。我们的工作将借鉴线性和凸优化、随机优化和最优停止理论以及在线学习的思想，以加深我们对不确定性下优化中的这些和其他核心问题的理解。该奖项反映了 NSF 的法定使命，并被认为是值得的通过使用基金会的智力优势和更广泛的影响审查标准进行评估来获得支持。

项目成果

Graph Searching with Predictions

带有预测的图搜索

• 发表时间: 2023-01
• 期刊: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023
• 作者: Banerjee, Siddhartha;Cohen;Gupta, Anupam;Li, Zhouzi
• 通讯作者: Li, Zhouzi

Learning from a Sample in Online Algorithms

从在线算法中的样本中学习

• 发表时间: 2022-01
• 期刊: NeurIPS 2022
• 作者: Argue, C.J.;Frieze, Alan;Gupta, Anupam;Seiler, Christopher
• 通讯作者: Seiler, Christopher

Minimizing Completion Times for Stochastic Jobs via Batched Free Times

通过批量空闲时间最小化随机作业的完成时间

• 发表时间: 2023-01
• 期刊: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Gupta, Anupam;Moseley, Benjamin;Zhou, Rudy
• 通讯作者: Zhou, Rudy

Augmenting Online Algorithms with epsilon-Accurate Predictions

使用 epsilon 准确预测增强在线算法

• 发表时间: 2022-01
• 期刊: NeurIPS 2022
• 作者: Gupta, Anupam;Panigrahi, Debmalya;Subercaseaux, Bernardo;Sun, Kevin
• 通讯作者: Sun, Kevin

Configuration Balancing for Stochastic Requests

随机请求的配置平衡

• 发表时间: 2023-01
• 期刊: Integer Programming and Combinatorial Optimization (IPCO
• 作者: Eberle, Franziska;Gupta, Anupam;Megow, Nicole;Moseley, Benjamin;Zhou, Rudy
• 通讯作者: Zhou, Rudy