.png){kind=icon}
.png){kind=icon}
Return
Dynamic Necklace Splitting
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.ICDT.2026.19.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Necklace splitting
dynamic algorithms
fair division
Journal
2
IF:
0
Papers:
28
Citations:
0
