AF:Small:Beyond Worst Case Running time: Algorithms for Routing, Scheduling and Matching

AF：小：超越最坏情况运行时间：路由、调度和匹配算法

• 批准号: 1714818
• 负责人: Clifford Stein
• 金额: $ 45.68万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714818&HistoricalAwards=false
• 关键词: AF; Small; Beyond; Worst; Case

Algorithms are ubiquitous and influence many important aspects of our lives. They address decisions ranging from the mundane, e.g. which movie to watch, to the vitally important, e.g. how to manage the internet or to schedule some time-critical tasks in a navigation system. Even though computing power and network bandwidth increase at a rapid rate, users and applications increase their demand for computation and their use of networks at roughly the same pace. Thus, a critical bottleneck in many important technologies and applications is an algorithm.The problems considered in this project, mainly matching, scheduling and routing are fundamental algorithmic problems. By looking at resources such as energy, machines needed, and reassignments, the project will significantly broaden and deepen our understanding of these basic algorithmic problems. It will also design simpler algorithms that will lead to easily implementable solutions. The PI will make progress both in theory and in practice and will disseminate his results. The project will also make significant contributions to education via PI's textbook and other new materials. The PI will continue his commitment to Ph.D. student diversity.It is now well-understood that time, space and worst-case solution quality are not the only resources that need to be optimized. For the past few decades, there has been a growing emphasis on other concerns such as availability of information, use of cache, management of disk, etc. More recently, there has been a growing understanding that energy and power management are also resources that should be carefully managed. In addition, one may also be interested in features of solutions as they evolve over time, or one may be interested in the algorithm's use of resources such as machines, processing speed or updates. Finally, one may also be interested in not just the bounds that we improve, but also the real-life performance of important problems.This project plans to study several algorithmic problems that arise in scheduling, routing and matchings. The PI intends to make progress on some traditional problems and their variants and is particularly interested in considering problems from novel perspectives, that is, considering metrics that go beyond the traditionally studied ones. In particular, the project will consider energy consumption in both computers and networks, and will also consider environments in which other resources must be managed, such as minimizing the number of changes to a solution over time, the amount of processing power needed to compute a solution, or the algorithm's response to a changing environment.

算法无处不在，影响着我们生活的许多重要方面。他们解决的决策范围从平凡的，例如看哪部电影，对于至关重要的事情，例如如何管理互联网或在导航系统中安排一些时间紧迫的任务。尽管计算能力和网络带宽快速增长，但用户和应用程序对计算的需求和网络使用的增长速度大致相同。因此，很多重要技术和应用的关键瓶颈就是算法。本项目考虑的问题主要是匹配、调度和路由，都是基础算法问题。通过研究能源、所需机器和重新分配等资源，该项目将显着拓宽和加深我们对这些基本算法问题的理解。它还将设计更简单的算法，从而产生易于实施的解决方案。 PI 将在理论和实践上取得进展，并将传播他的成果。该项目还将通过PI的教科书和其他新材料为教育做出重大贡献。 PI 将继续致力于攻读博士学位。学生多样性。现在众所周知，时间、空间和最坏情况解决方案质量并不是唯一需要优化的资源。在过去的几十年里，人们越来越重视其他问题，例如信息的可用性、缓存的使用、磁盘的管理等。最近，人们越来越认识到能源和电源管理也是应该考虑的资源。进行精心管理。此外，人们还可能对解决方案随着时间的推移而演变的特征感兴趣，或者人们可能对算法对资源（例如机器、处理速度或更新）的使用感兴趣。最后，人们可能不仅对我们改进的范围感兴趣，还对重要问题的现实表现感兴趣。该项目计划研究调度、路由和匹配中出现的几个算法问题。 PI 打算在一些传统问题及其变体上取得进展，并且特别有兴趣从新颖的角度考虑问题，即考虑超越传统研究指标的指标。特别是，该项目将考虑计算机和网络的能源消耗，还将考虑必须管理其他资源的环境，例如最大限度地减少解决方案随时间的变化次数、计算计算所需的处理能力。解决方案，或算法对不断变化的环境的响应。

项目成果

Estimating the Longest Increasing Subsequence in Nearly Optimal Time

估计接近最佳时间的最长递增子序列

• DOI: 10.1109/focs54457.2022.00073
• 发表时间: 2021-12-09
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Ale;r Andoni;r;Negev Shekel Nosatzki;S. Sinha;C. Stein
• 通讯作者: C. Stein

A Competitive Algorithm for Throughput Maximization on Identical Machines

一种在相同机器上实现吞吐量最大化的竞争算法

• 发表时间: 2022-06
• 期刊: Integer Programming and Combinatorial Optimization
• 作者: Moseley, Benjamin;Pruhs, Kirk;Stein, Clifford;Zhou, Rudy
• 通讯作者: Zhou, Rudy

Matching Drivers to Riders: ATwo-Stage Robust Approach

将驾驶员与乘客匹配：两阶段稳健方法

• 发表时间: 2021-09
• 期刊: and Combinatorial Optimization. Algorithms and Techniques
• 作者: El Housni, Omra;Goyal, Vineet;Hanguir, Oussama;Stein, Clifford
• 通讯作者: Stein, Clifford

Incremental Edge Orientation in Forests

森林中的增量边缘方向

• DOI: 10.4230/lipics.esa.2021.12
• 发表时间: 2021-01
• 期刊: Proc.\ 28th Annual European Symposium on Algorithms (ESA
• 作者: Bender, Michael A.;Kopelowitz, Tsvi;Kuszmaul, William;Porat, Ely;Stein, Clifford
• 通讯作者: Stein, Clifford

A general framework for handling commitment in online throughput maximization

处理在线吞吐量最大化承诺的通用框架

• DOI: 10.1007/s10107-020-01469-2
• 发表时间: 2020-09
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Chen, Lin;Eberle, Franziska;Megow, Nicole;Schewior, Kevin;Stein, Cliff
• 通讯作者: Stein, Cliff