ComputingComputer ScienceAlgorithmsDistributed SystemsSchedulingInteger ProgrammingJob SchedulingMachine SchedulingResource AllocationResource-constrained SchedulingScheduling TheoryAllocation Of Indivisible GoodsFair DivisionFair Resource AllocationFair Resource SharingFairnessMulti-agent Resource Allocation
We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With our algorithm, we can always find a 11/9-approximation maximin share allocation for any instance. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem. The full paper can be found at https://arxiv.org/abs/1907.04505.
24
Consistent Estimates Based on Partially Consistent Observations
Jerzy Neyman, Elizabeth L. Scott · Econometrica · 1948 · 2.7K citations
Bounds for Certain Multiprocessing Anomalies
Ronald Graham · Bell System Technical Journal · 1966 · 1.6K citations
Resource allocation and the public sector
Delia Foley · Medical Entomology and Zoology · 1967 · 1.1K citations
On approximately fair allocations of indivisible goods
R.J. Lipton, Evangelos Markakis, Elchanan Mossel et al. · 2004 · 530 citations