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打算在一些传统问题及其变体上取得进展，并且特别感兴趣的是从新的角度考虑问题，即考虑超越传统研究的指标。特别是，该项目将考虑计算机和网络的能源消耗，还将考虑必须管理其他资源的环境，例如最大限度地减少随时间变化的解决方案的数量，计算解决方案所需的处理能力，或算法对不断变化的环境的响应。

项目成果

Matching Drivers to Riders: A Two-Stage Robust Approach

• DOI: 10.4230/lipics.approx/random.2021.12
• 发表时间: 2020-11
• 作者: Omar El Housni;Vineet Goyal;Oussama Hanguir;C. Stein

Estimating the Longest Increasing Subsequence in Nearly Optimal Time

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

A Competitive Algorithm for Throughput Maximization on Identical Machines

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

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

Incremental Edge Orientation in Forests

森林中的增量边缘方向

• DOI: 10.4230/lipics.esa.2021.12
• 发表时间: 2021
• 期刊: 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
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Chen, Lin;Eberle, Franziska;Megow, Nicole;Schewior, Kevin;Stein, Cliff
• 通讯作者: Stein, Cliff