Abstract-Vi anser att Max-Min Allokering problem: med tanke på en uppsättning A av m agenter och en uppsättning I av n objekt, där agent A  på A har verktyg uA, i för objekt i I, vårt mål är att fördela objekt till agenter för att maximera rättvisa. Specifikt är nyttan av en agent summan av dess verktyg för de objekt den tar emot, och vi försöker maximera den minsta nyttan av någon agent. Även om detta problem har fått mycket uppmärksamhet på senare tid, dess approximabilitet har inte varit väl förstådd hittills: den mest kända approximationsalgoritmen uppnår en Õ( ε m)- approximation, och i kontrast, den mest kända hårdheten av approximationen står på 2. Vårt huvudsakliga resultat är en algoritm som uppnår en Õ(n)-uppskattning för någon =  och ( log n log n ) i tid n O(1/ ). I synnerhet får vi poly-logaritmisk approximation i kvasipolynom tid, och för varje konstant > 0, vi får añ O (n ) - approximation i polynom tid. En intressant teknisk aspekt av vår algoritm är att vi som ett byggblock använder ett linjärt program vars integralitetsgap är -( ε m). Vi kringgår detta hinder genom att iterativt använda de lösningar som produceras av LP för att konstruera nya fall med betydligt mindre integreradhet luckor, så småningom få önskad approximation. Som en följd av vårt huvudsakliga resultat, visar vi också att för varje konstant > 0, en O (m )-uppskattning kan uppnås i kvasi-polynom tid. Vi undersöker också det speciella fallet av problemet, där varje objekt har non-noll nytta för högst två agenter. Detta problem är svårt att närma upp till någon faktor bättre än 2. Vi ger en faktor 2- approximationsalgoritm.
Slutligen noterar vi att Chakrabarti, Chuzhoy och Khanna REF använde en samling flödesproblem för att få fram förbättrade approximationsalgoritmer för problemet med maxminallokering.
On Allocating Goods to Maximize Fairness
{'venue': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}