|国家预印本平台
首页|Lower Bound for Online MMS Assignment of Indivisible Chores

Lower Bound for Online MMS Assignment of Indivisible Chores

Lower Bound for Online MMS Assignment of Indivisible Chores

来源:Arxiv_logoArxiv
英文摘要

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.

Masoud Seddighin、Saeed Seddighin

计算技术、计算机技术

Masoud Seddighin,Saeed Seddighin.Lower Bound for Online MMS Assignment of Indivisible Chores[EB/OL].(2025-07-17)[2025-08-16].https://arxiv.org/abs/2507.12984.点此复制

评论