Theory Seminar: Scheduling and Resource Allocation Problems in Multidimensional Settings

Friday, April 15, 2016 - 2:00pm
CS 4310

Speaker Name: 

Janardhan Kulkarni

Speaker Institution: 

Microsoft Research

Cookies: 

Yes

Cookies Location: 

CS 4310

Description: 

Scheduling jobs is a fundamental combinatorial problem that arises in various forms in many scenarios. Motivated by applications in data center settings, we study a very general multidimensional scheduling problem. Here, jobs can have different resource requirements, arrival times and sizes, and the rates at which a scheduler can process jobs are subject to arbitrary packing constraints. The problem captures a broad class of scheduling problems, including several classical scheduling problems.

We design non-clairvoyant, stateless, online algorithms for this problem and its special cases. Our algorithms make scheduling decisions without knowing the future input or keeping track of the past, and do not even have to know the job sizes until their completion. Algorithmically interesting aspect of our work is that our algorithms have surprising connections to concepts from game theory and economics, and are very different from more classical scheduling algorithms.

Speaker's bio: Janardhan Kulkarni is a postdoctoral researcher in the theory group at Microsoft Research, Redmond. He obtained his Ph.D. from the department of computer science at Duke University, Durham. Kulkarni's primary research interest is in the design of algorithms with provable performance guarantees. His current focus is on resource allocation and scheduling problems that arise in large scale data centers, with practical constraints such as fairness, energy minimization etc. Kulkarni's research uses concepts and techniques from the fields of approximation algorithms, online algorithms, game theory, and learning theory. Kulkarni's research has appeared in the top algorithms and game theory venues such as STOC, FOCS, SODA, and EC. He is a recipient of Duke Best Thesis Award 2015, Duke Teaching and Mentoring Award 2013, and a Gold medal from the Indian Institute of Science 2010.