CAREER: Adaptive Algorithms for Combinatorial Optimization in Stochastic Networks

职业：随机网络中组合优化的自适应算法

• 批准号: 1652115
• 负责人: Javad Ghaderi
• 金额: $ 50.27万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1652115&HistoricalAwards=false
• 关键词: CAREER; Adaptive; Algorithms; Combinatorial; Optimization

This project introduces a new randomized algorithmic framework for solving difficult combinatorial and time-varying problems. The key approach in the proposed framework is to cleverly perturb each objective function to make the problem more tractable while still guaranteeing that the approximate solution is within some constant factor of the solution to the original objective function. The project specifically focuses on tackling scheduling in wireless and data center networks, where solutions to the static problem version are computationally hard. Hence the results could improve the performance of next generation data centers and advanced wireless technologies, thus benefitting the US economy.The proposed project will (1) create a coherent mathematical framework for stochastic combinatorial optimization; (2) design scalable algorithms for decentralized medium access control in emerging wireless networks with modern requirements, and high-performance scheduling algorithms for executing jobs in datacenters; and (3) demonstrate the gains in practice, evaluating the performance of the proposed algorithms over prior approaches using a combination of simulations and experiments.

这个项目介绍了一种新的随机化算法框架，用于解决困难的组合和时变问题。该框架的关键是巧妙地对每个目标函数进行扰动，使问题变得更容易处理，同时保证近似解在原目标函数解的某个恒定因子内。该项目特别关注解决无线和数据中心网络中的调度问题，在这些网络中，静态问题的解决方案很难计算。该项目将(1)为随机组合优化建立一个连贯的数学框架；(2)为满足现代需求的新兴无线网络中的去中心化媒体访问控制设计可扩展的算法，以及在数据中心执行作业的高性能调度算法；(3)通过模拟和实验相结合的方法对所提出的算法的性能进行评估。

项目成果

Online scheduling and routing with end-to-end deadline constraints in multihop wireless networks

多跳无线网络中具有端到端期限约束的在线调度和路由

• DOI: 10.1145/3492866.3549729
• 发表时间: 2022
• 期刊: ACM
• 作者: Tsanikidis, Christos;Ghaderi, Javad
• 通讯作者: Ghaderi, Javad

On Non-Preemptive VM Scheduling in the Cloud

• DOI: 10.1145/3219617.3219644
• 发表时间: 2017-12
• 期刊: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems
• 作者: Konstantinos Psychas;Javad Ghaderi

An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in Datacenters

• DOI: 10.1109/tnet.2018.2845852
• 发表时间: 2017-04
• 期刊: IEEE/ACM Transactions on Networking
• 作者: Mehrnoosh Shafiee;Javad Ghaderi

Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints

• DOI: 10.1287/opre.2021.2198
• 发表时间: 2020-04
• 期刊: ArXiv
• 作者: Mehrnoosh Shafiee;Javad Ghaderi

A simple congestion-aware algorithm for load balancing in datacenter networks

• DOI: 10.1109/tnet.2017.2751251
• 发表时间: 2016-04
• 期刊: IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications
• 作者: Mehrnoosh Shafiee;Javad Ghaderi