View all Seminars  |  Download ICal for this event

Optimal Resource Allocation Problems in Large-Scale Networks

Series: Department Seminar

Speaker: Dr. Abhishek Sinha, Assistant Professor, Department of Electrical Engineering, Indian Institute of Technology Madras,

Date/Time: Nov 29 16:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

Optimal resource allocation in networks gives rise to some of the most fundamental problems at the intersection of algorithms, stochastic processes, and learning. In this talk, we will discuss our recent contributions to three canonical resource allocation problems, namely caching, routing, and scheduling. First, we will consider the optimal caching problem in both stand-alone and networked settings. However, instead of minimizing the competitive ratio - the classical metric of choice for caching problems, we will look at the problem from an online learning perspective that aims to minimize the regret. We will show that this viewpoint leads to an entirely new class of caching policies with provably better performance than the classical ones. We will also discuss some tight regret lower bounds for this problem. Next, we will consider the problem of throughput-optimal dynamic routing of a broad traffic class, including unicast, multicast, broadcast, and anycast flows on a network with arbitrary link scheduling constraints. We will present a unified algorithmic framework based on precedence relaxations, leading to an efficient policy that provably outperforms the state-of-the-art Backpressure routing algorithm. Finally, we will discuss the user scheduling problem for reliable and fresh information delivery over unreliable wireless channels. However, contrary to the existing literature, which predominantly considers stochastic channels, we investigate a non-stationary environment modeled using a new adversarial framework. We will describe competitive algorithms in this setting along with some tight lower bounds. We will supplement each part of the talk with a set of open problems.

Speaker Bio:
Abhishek Sinha is currently an Assistant Professor in the Department of Electrical Engineering at the Indian Institute of Technology Madras. He received his Ph.D. degree from the Massachusetts Institute of Technology in 2017, where he was affiliated with the Laboratory for Information and Decision Systems (LIDS). After his Ph.D., Abhishek worked as a senior engineer at Qualcomm Research, San Diego, in the 5G standardization group. He obtained his M.E. degree in Telecommunication Engg. from the Indian Institute of Science, Bangalore, and B.E. degree in Electronics and Telecommunication Engg. from Jadavpur University, Kolkata, India. He is a recipient of the INSA Medal for Young Scientist (2021), Best Paper Awards in INFOCOM 2018 and MobiHoc 2016, Prof. Jnansaran Chatterjee memorial gold medal, and T.P. Saha Memorial gold-centered silver medal from Jadavpur University and Jagadis Bose National Science Talent Search (JBNSTS) scholarship, Kolkata, India. His areas of interest include networks, information theory, theoretical machine learning, and applied probability.

Microsoft teams link:

Host Faculty: Prof. Chiranjib Bhattacharyya