English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the maximin share (MMS) fair allocation of $m$ indivisible chores to$n$ agents who have costs for completing the assigned chores. It is known thatexact MMS fairness cannot be guaranteed, and so far the best-knownapproximation for additive cost functions is $\frac{13}{11}$ by Huang andSegal-Halevi [EC, 2023]; however, beyond additivity, very little is known. Inthis work, we first prove that no algorithm can ensure better than$\min\{n,\frac{\log m}{\log \log m}\}$-approximation if the cost functions aresubmodular. This result also shows a sharp contrast with the allocation ofgoods where constant approximations exist as shown by Barman and Krishnamurthy[TEAC, 2020] and Ghodsi et al. [AIJ, 2022]. We then prove that for subadditivecosts, there always exists an allocation that is $\min\{n,\lceil\logm\rceil\}$-approximation, and thus the approximation ratio is asymptoticallytight. Besides multiplicative approximation, we also consider the ordinalrelaxation, 1-out-of-$d$ MMS, which was recently proposed by Hosseini et al.[JAIR and AAMAS, 2022]. Our impossibility result implies that for any $d\ge 2$,a 1-out-of-$d$ MMS allocation may not exist. Due to these hardness results forgeneral subadditive costs, we turn to studying two specific subadditive costs,namely, bin packing and job scheduling. For both settings, we show thatconstant approximate allocations exist for both multiplicative and ordinalrelaxations of MMS.

Fair Allocation of Indivisible Chores: Beyond Additive Costs