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-服务器及其推广的可扩展的、鲁棒的凸松弛，并利用这些松弛得到好的算法;（c）为典型情况制定一个更广泛的框架，而不是侧重于最坏的情况。我们的工作将借鉴线性和凸优化、随机优化和最优停止理论以及在线学习的思想，以加深我们对这些以及不确定性优化中其他核心问题的理解。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

A Local Search-Based Approach for Set Covering

基于局部搜索的集合覆盖方法

• 发表时间: 2023
• 期刊: 2023 Symposium on Simplicity in Algorithms (SOSA
• 作者: Gupta, Anupam;Lee, Euiwoong;Li, Jason
• 通讯作者: Li, Jason

Graph Searching with Predictions

• DOI: 10.48550/arxiv.2212.14220
• 发表时间: 2022-12
• 作者: Sid Banerjee;Vincent Cohen-Addad;Anupam Gupta;Zhou Li

Minimizing Completion Times for Stochastic Jobs via Batched Free Times

• DOI: 10.48550/arxiv.2208.13696
• 发表时间: 2022-08
• 作者: Anupam Gupta;Benjamin Moseley;Rudy Zhou

Configuration Balancing for Stochastic Requests

随机请求的配置平衡

• 发表时间: 2023
• 期刊: integer programming and combinatorial optimization
• 作者: Eberle, F.;Gupta, A.;Megow, N.;Moseley, B.;Zhou, R.
• 通讯作者: Zhou, R.

Augmenting Online Algorithms with epsilon-Accurate Predictions

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

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