{"ID":2893457,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12984","arxiv_id":"2507.12984","title":"Lower Bound for Online MMS Assignment of Indivisible Chores","abstract":"We consider the problem of online assignment of indivisible chores under \\MMS\\ criteria. The previous work proves that any deterministic online algorithm for chore division has a competitive ratio of at least 2. In this work, we improve this bound by showing that no deterministic online algorithm can obtain a competitive ratio better than $n$ for $n$ agents.","short_abstract":"We consider the problem of online assignment of indivisible chores under \\MMS\\ criteria. The previous work proves that any deterministic online algorithm for chore division has a competitive ratio of at least 2. In this work, we improve this bound by showing that no deterministic online algorithm can obtain a competiti...","url_abs":"https://arxiv.org/abs/2507.12984","url_pdf":"https://arxiv.org/pdf/2507.12984v1","authors":"[\"Masoud Seddighin\",\"Saeed Seddighin\"]","published":"2025-07-17T10:39:27Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}