BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20211129T120000Z
UID:a34bc696360e33678a420d4e509c4945-223
DTSTAMP:19700101T120016Z
DESCRIPTION:Optimal Resource Allocation Problems in Large-Scale Networks
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/223/optimal-resource-allocation-problems-in-large-scale-networks/
SUMMARY: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.
DTSTART:20211129T120000Z
END:VEVENT
END:VCALENDAR