Algorithms and Lower Bounds for the Worker-Task Assignment Problem
share
We study the problem of assigning workers to tasks where each task has demand for a particular number of workers, and the demands are dynamically changing over time. Specifically, a worker-task assignment function ϕ takes a multiset of w tasks T ⊆ [t] and produces an assignment ϕ(T) from the workers 1, 2, …, w to the tasks T. The assignment function ϕ is said to have switching cost at most k if, for all task multisets T, changing the contents of T by one task changes ϕ(T) by at most k worker assignments. The goal of the worker-task assignment problem is to produce an assignment function ϕ with the minimum possible switching cost. Prior work on this problem (SSS'17, ICALP'20) observed a simple assignment function ϕ with switching cost min(w, t - 1), but there has been no success in constructing ϕ with sublinear switching cost. We construct the first assignment function ϕ with sublinear, and in fact polylogarithmic, switching cost. We give a probabilistic construction for ϕ that achieves switching cost O(log w log (wt)) and an explicit construction that achieves switching cost polylog (wt). From the lower bounds side, prior work has used involved arguments to prove constant lower bounds on switching cost, but no super-constant lower bounds are known. We prove the first super-constant lower bound on switching cost. In particular, we show that for any value of w there exists a value of t for which the optimal switching cost is w. That is, when w ≪ t, the trivial bound on switching cost is optimal. We also consider an application of the worker-task assignment problem to a metric embeddings problem. In particular, we use our results to give the first low-distortion embedding from sparse binary vectors into low-dimensional Hamming space.
READ FULL TEXT