TDT24
(1) 2024 A Reduction from Chores Allocation to Job Scheduling
(2) 2023 A Survey on Fair Allocation of Chores
The fair allocation of chores can be seen as a scheduling problem for unrelated parallel machines (RCmax). The chore corresponds to the job. The agent corresponds to the unrelated parallel machine. In the fair allocation problem of chores, the disutility of each agent for each chore can be seen as the time consumed by each machine to process each job in the scheduling problem.
(3) 2021 An algorithmic framework for approximating maximin share allocation of chores
(4) Algorithms for Max-Min Share Fair Allocation of Indivisible Chores
-
MmS allocations of goods are being used in practice for fair division in real-world problems (Goldman and Procaccia 2014).
-
there has been less research on chore allocation compared to goods despite there being many settings where we have chores but not goods (Brams and Taylor 1996).
-
An extensive overview on all important machine scheduling problems is provided by Pinedo (2012).
-
We tested different instance sizes with a varying number of agents N ∈ {2,4,8,16,32,64,128} and items M ∈ {N,2N,3N,4N,6N,8N,10N,15N,20N,25N} by generating 10 instances per instance size and averaging the results. The time limit in step 4 of SCHED was set to Tmax = 300s. Utilities were drawn from a uniform distri bution ui(j) ∼ U(0,100) (and negated forobtaining chores instances) as it is common in the literature for fair division of goods (Amanatidis et al. 2015; Bouveret and Lemaˆıtre 2016; Kurokawa, Procaccia, and Wang 2016).
-
We were not able to calculate optimal MmS ratios for instance sizes with N ≥ 16.
(5) Exact and Approximate Algorithms for Scheduling Nonidentical Processors
Hans-Marius
- Fairly Allocating Goods in Parallel (https://doi.org/10.48550/arXiv.2309.08685)
- A parallel integer linear programming algorithm (https://doi.org/10.1016/0377-2217(88)90160-9)
- Parallel Combinatorial Optimization with Decision Diagrams (https://doi.org/10.1007/978-3-319-07046-9_25)
- Parallel algorithms for bipartite matching problems on distributed memory computers (https://doi.org/10.1016/j.parco.2011.09.004)
- Parallelization of Bin Packing on Multicore Systems (https://doi.org/10.1109/HiPC.2016.044)
Options
- Haris Aziz, Hau Chan, and Bo Li. Maxmin share fair allocation of indivisible chores to asymmetric agents. In Proc. 18th Conf. Auton. Agents and Multi-Agent Systems (AAMAS), pages 17871789, 2019.
- Haris Aziz, Hau Chan, and Bo Li. Weighted maxmin fair share allocation of indivisible chores. In Proc. 28th Intl. Joint Conf. Artif. Intell. (IJCAI), 2019.
- Simina Branzei and Fedor Sandomirskiy. Algorithms for competitive division of chores. arXiv:1907.01766, 2019.
- Feige, U.; Huang, X. On picking sequences for chores. arXiv 2022, arXiv:2211.13951.