CANCELLED
Title: On the Power of Randomization for Combinatorial Scheduling in Stochastic Networks
Abstract: Many problems of both theoretical and practical importance that arise in optimizing modern stochastic networks are hard combinatorial problems. This talk focuses on two such problems in the context of wireless networks and data centers, namely, (1) scheduling deadline-constrained packets in emerging wireless networks, and (2) scheduling resource-constrained tasks in data centers.
In the first problem, the objective is to maximize the fraction of packets of each link that are delivered within their deadlines (a.k.a. delivery ratio). This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (largest-deficit first). Through a careful randomization over the maximal schedules at each time, we design randomized algorithms that can achieve delivery ratios much higher than what is achievable by LDF. Further, the results apply to traffic (arrival and deadline) processes that evolve as a unknown Markov chain. In the second problem, the objective is to maximize throughput, by packing as many tasks as possible in servers, while not exceeding servers' capacity constraints. We first show that greedy bin packing heuristics can lead to a poor performance, but Best-Fit can be modified to achieve at least 1/2 of the optimal throughput. Then we design randomized algorithms that can achieve near-optimal throughput with low complexity. The talk will demonstrate the crucial role that randomization can play in algorithm design in stochastic networks.
Bio:
Javad Ghaderi is an Associate Professor of Electrical Engineering at Columbia University. His research interests include algorithms, optimization, and stochastic processes with application to communication networks and data centers. He received his Ph.D. from the University of Illinois at Urbana-Champaign in 2013. He spent a one-year Simons Postdoctoral Fellowship at the University of Texas at Austin before joining Columbia. He is the recipient of several awards including Best Student Paper Finalist at 2013 American Control Conference (ACC), Best Paper Award at ACM CoNEXT 2016, and NSF CAREER Award in 2017.
-----------------------------------------------------------------------------------------------------
