Seminar Details
The Worker-Task Assignment Problem
- Start Date: September 30, 2020
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Organizers: Sepehr Assadi || Swastik Kopparty
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Nicole Wein - Massachusetts Institute of Technology
- Event Location: Online Event
- Event Additional Info: <p>The <strong>Theory of Computing Seminar is being held online. </strong>Contact the organizers for the link to the seminar.</p>
- Presentation Type: Stand Alone Presentation
- 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.