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.