# Seminars & Colloquia Calendar

## The Worker-Task Assignment Problem

#### Nicole Wein (MIT)

Location: ** https://theory.cs.rutgers.edu/theory_seminar**

Date & time: Wednesday, 30 September 2020 at 11:00AM - 12:00PM

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.

Chiara Damiolini, Ian Coley and Franco Rota -Charles Weibel Organizer's Page

Narek Hovsepyan and Ewerton Rocha Vieira Organizer's page

Ziming Shi, Sagun Chanillo, Xiaojun Huang, Chi Li, Jian Song Seminar website Old seminar website

Sepehr Assadi Seminar webpage

Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage

Robert Dougherty-Bliss and Doron Zeilberger --> homepage

Paul Feehan, Daniel Ketover, Natasa Sesum Organizer's webpage

Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage

Hong Chen Seminar webpage

Fanxin Wu and Nkhalo Malawo Organizer's website

James Holland; Organizer website

Organizers: Maxime Van de Moortel and Avy Soffer. Organizer's Page

Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum Organizer's Webpage

Organizer: Luochen Zhao

Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song Organizer's Page

Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage

Simon Thomas website

Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page

Joel Lebowitz, Michael Kiessling

Yanyan Li, Dennis Kriventsov Organizer's Webpage

Alex V. Kontorovich, Vlada Sedláček seminar website

Stephen D. Miller

Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum

Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page

Fioralba Cakoni Seminar webpage

- Show events from all categories

## Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

*Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.*