Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Nicole Wein, Massachusetts Institute of Technology

Abstract

I will talk about the Worker-Task Assignment Problem, where the goal is to assign workers to tasks where each task has demand for a particular number of workers, and the demands are dynamically changing over time. The formalization of this problem that I will discuss is a combinatorics problem at its core, but was introduced in the context of distributed algorithms and also has applications to metric embeddings.

The problem is defined as follows: There are w workers and t tasks, and a worker-task assignment function F is a function that takes as input a multiset T of w tasks and produces an assignment F(T) from the workers to the tasks T. The assignment function F is said to have switching cost at most k if, for all task multisets T, changing the contents of T by one task changes F(T) by at most k worker assignments. The goal of the worker-task assignment problem is to produce an assignment function F with the minimum possible switching cost. 

In this talk I will discuss the best known upper and lower bounds for this problem, between which there is still a large gap.

Based on joint work with Aaron Berger, William Kuszmaul, Adam Polak, Hsin-Hao Su, and Jonathan Tidor.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.