DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2026.19

Dynamic Necklace Splitting

Authors: Rishi Advani, Abolfazl Asudeh, Mohsen Dehghankar, and Stavros Sintos

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

The necklace splitting problem is a classic problem in fair division with many applications, including data-informed fair hash maps. We extend necklace splitting to a dynamic setting, allowing for relocation, insertion, and deletion of beads. We present linear-time, optimal algorithms for the two-color case that support all dynamic updates. For more than two colors, we give linear-time, optimal algorithms for relocation subject to a restriction on the number of agents. Finally, we propose a randomized algorithm for the two-color case that handles all dynamic updates, guarantees approximate fairness with high probability, and runs in polylogarithmic time when the number of agents is small.

Cite as

Rishi Advani, Abolfazl Asudeh, Mohsen Dehghankar, and Stavros Sintos. Dynamic Necklace Splitting. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{advani_et_al:LIPIcs.ICDT.2026.19,
  author =	{Advani, Rishi and Asudeh, Abolfazl and Dehghankar, Mohsen and Sintos, Stavros},
  title =	{{Dynamic Necklace Splitting}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.19},
  URN =		{urn:nbn:de:0030-drops-256332},
  doi =		{10.4230/LIPIcs.ICDT.2026.19},
  annote =	{Keywords: Necklace splitting, dynamic algorithms, fair division}
}

Search Results

Documents authored by Dehghankar, Mohsen

Dynamic Necklace Splitting

Abstract

Cite as

Thanks for your feedback!

Could not send message