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

In this paper we study the relation of two fundamental problems in schedulingand fair allocation: makespan minimization on unrelated parallel machines andmax-min fair allocation, also known as the Santa Claus problem. For both ofthese problems the best approximation factor is a notorious open question; moreprecisely, whether there is a better-than-2 approximation for the formerproblem and whether there is a constant approximation for the latter.  While the two problems are intuitively related and history has shown thattechniques can often be transferred between them, no formal reductions areknown. We first show that an affirmative answer to the open question formakespan minimization implies the same for the Santa Claus problem by reducingthe latter problem to the former. We also prove that for problem instances withonly two input values both questions are equivalent.  We then move to a special case called ``restricted assignment'', which iswell studied in both problems. Although our reductions do not maintain thecharacteristics of this special case, we give a reduction in a slightgeneralization, where the jobs or resources are assigned to multiple machinesor players subject to a matroid constraint and in addition we have only twovalues. This draws a similar picture as before: equivalence for two values andthe general case of Santa Claus can only be easier than makespan minimization.To complete the picture, we give an algorithm for our new matroid variant ofthe Santa Claus problem using a non-trivial extension of the local searchmethod from restricted assignment. Thereby we unify, generalize, and improveseveral previous results. We believe that this matroid generalization may be ofindependent interest and provide several sample applications.

Santa Claus meets Makespan and Matroids: Algorithms and Reductions