Abstrakt. I detta dokument ger vi den första approximationsalgoritmen för problemet med maximal-min rättvis fördelning av odelbara varor. Ett exempel på detta problem är en uppsättning k personer och m odelbara varor. Varje person har en känd linjär nyttofunktion över uppsättningen varor som kan skilja sig från andra människors nyttofunktioner. Målet är att distribuera varorna bland folket och maximera det minimum av nytta som de får. Den approximativa proportionen av vår algoritm är en avgörande del av vår algoritm, vi utforma och analysera en iterativ metod för avrundning en fraktionerad matchning på ett träd som kan vara av oberoende intresse. Vi ger också bättre gränser när vi tillåts utesluta en liten del av folket från problemet. 1. Vad är det för fel på dig? Inledning. Rättvis uppdelning, även känd som kaka skär problemet, har studerats i stor utsträckning, mestadels med ett mått teoretiskt eller kombinatoriskt perspektiv i matematik litteratur sedan 1950-talet [26]. På senare tid har detta problem uppmärksammats av datavetenskapssamfundet, där tonvikten ligger mer på att utforma effektiva algoritmer [24, 21, 22]. Att gå bortom metaforen av kaka, fokuserar de flesta av dessa verk på praktiska fall där varorna är mindre delbara. En intresserad läsare kan konsultera [9] för en lång lista med tillämpningar av dessa problem. I detta dokument studerar vi problemet med en rättvis fördelning av odelbara varor med maxmineral. I vår miljö fördelar vi m varor till k personer. Varje person i har en icke-negativ heltal värdering u ij för bra j. Vi utgår från att värderingsfunktionerna är linjära, dvs. u i,C = j och C u ij för varje uppsättning C av varor. Målet är att fördela varje vara till en person så att den som är minst lycklig är så lycklig som möjligt. Mer formellt vill vi maximera min i u i,Ci, där C i är den uppsättning varor som tilldelas person i. Detta problem är till sin natur mycket likt problem med arbetsschemaläggningen, särskilt minimala makespan schemaläggning [23]. Tillämpningar av tekniker som avrundning av uppdrag linjära programmet [8, 16] har dock inte gett algoritmer med ett approximationsförhållande bättre än O(1/k) för detta problem hittills. Den tilldelade LP som används i [23] ger en additiv approximation av max ij u ij [8], dvs. Det kan användas för att hitta en värdelösning minst OPT − max ij u ij, där OPT är värdet av den optimala lösningen. Tyvärr erbjuder det ingen multiplikativ approximation garanti i de mest utmanande fall av problemet när OPT ≤ max ij u ij. När det gäller subadditiva allmännyttiga funktioner tillhandahåller Khot och Ponnuswami [20] en (2k − 1)-tillnärmningsalgoritm. Bezakova och Dani [8] visade att detta problem är svårt att tillnärma inom en faktor som är bättre än
Därefter tillhandahöll Ref ett avrundningssystem för denna LP för att uppnå en genomförbar värdelösning som inte var sämre än O(
An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}