2026-07-28T20:54:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25633 2026-06-23T12:04:09Z ddc:004 open_access

Dynamic Necklace Splitting Advani, Rishi Asudeh, Abolfazl Dehghankar, Mohsen Sintos, Stavros Necklace splitting dynamic algorithms fair division 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rishi Advani and Abolfazl Asudeh and Mohsen Dehghankar and Stavros Sintos 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.19 urn:nbn:de:0030-drops-256332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.19 eng https://creativecommons.org/licenses/by/4.0/legalcode