{"ID":2863030,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.00162","arxiv_id":"2510.00162","title":"Dynamic Necklace Splitting","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.","short_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 suppor...","url_abs":"https://arxiv.org/abs/2510.00162","url_pdf":"https://arxiv.org/pdf/2510.00162v2","authors":"[\"Rishi Advani\",\"Abolfazl Asudeh\",\"Mohsen Dehghankar\",\"Stavros Sintos\"]","published":"2025-09-30T18:34:31Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}