1 Search Results for "Tidor, Jonathan"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.19

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Authors: Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, and Nicole Wein

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers [w] to the tasks T based only on the current value of T. The assignment function ϕ is said to have switching cost at most k if, for every task multiset T, changing the contents of T by one task changes ϕ(T) by at most k worker assignments. The goal of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost. In past work, the problem of determining the optimal switching cost has been posed as an open question. There are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4 (ICALP 2020). We show that it is possible to achieve polylogarithmic switching cost. We give a construction via the probabilistic method that achieves switching cost O(log w log (wt)) and an explicit construction that achieves switching cost polylog (wt). We also prove a super-constant lower bound on switching cost: we show that for any value of w, there exists a value of t for which the optimal switching cost is w. Thus it is not possible to achieve a switching cost that is sublinear strictly as a function of w. Finally, we present 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.

Cite as

Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, and Nicole Wein. Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.ICALP.2022.19,
  author =	{Berger, Aaron and Kuszmaul, William and Polak, Adam and Tidor, Jonathan and Wein, Nicole},
  title =	{{Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.19},
  URN =		{urn:nbn:de:0030-drops-163608},
  doi =		{10.4230/LIPIcs.ICALP.2022.19},
  annote =	{Keywords: Distributed Task Allocation, Metric Embeddings, Probabilistic Method}
}

Refine by Author
1 Berger, Aaron
1 Kuszmaul, William
1 Polak, Adam
1 Tidor, Jonathan
1 Wein, Nicole

Refine by Classification
1 Mathematics of computing → Combinatorics
1 Theory of computation → Distributed algorithms
1 Theory of computation → Random projections and metric embeddings

Refine by Keyword
1 Distributed Task Allocation
1 Metric Embeddings
1 Probabilistic Method

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Tidor, Jonathan"

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Abstract

Cite as

Thanks for your feedback!

Could not send message