What type of study is this?

This is a Quantitative Study study.

October 19, 2025Open Access

Lower Bound for Online MMS Assignment of Indivisible Chores

Key Points

No deterministic online algorithm can achieve a competitive ratio better than n for n agents, indicating fundamental limitations.
Previous studies established a competitive ratio of at least 2 for online chore division, emphasizing previous theoretical bounds.
Improved understanding of online assignment dynamics aids in recognizing the limits of current algorithmic strategies.
This work refines the foundational limits of chore assignment, highlighting the challenges of fair distribution in online settings.

Abstract

We consider the problem of online assignment of indivisible chores under \ 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.

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper

Cite This Study

Seddighin et al. (Thu,) studied this question.

synapsesocial.com/papers/68f4b10d3d9d770bbc6970a5 https://doi.org/https://doi.org/10.48550/arxiv.2507.12984