CAREER: Adaptive Algorithms for Combinatorial Optimization in Stochastic Networks

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

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.