CAREER: Adaptive Algorithms for Combinatorial Optimization in Stochastic Networks

Columbia University, New York NY

Investigators

Abstract

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.