Den begränsade max-min rättvis tilldelning problem (även känd som den begränsade Santa Claus problem) är ett av få problem som har den spännande statusen att ha en bättre uppskattning algoritm än approximation algoritm. Ja, Asadpour m.fl. [2012] visade att en viss konfiguration LP kan användas för att uppskatta det optimala värdet inom en faktor på 1/(4 + ), för alla > 0, men samtidigt är det inte känt hur man effektivt hittar en lösning med en jämförbar prestandagaranti. En naturlig fråga som uppstår av deras arbete är om skillnaden mellan dessa garantier är inneboende eller beror på brist på lämpliga tekniker. Vi tar itu med detta problem genom att ge en nästan polynomal approximationsalgoritm med nämnda prestandagaranti. Mer specifikt, vi modifierar den lokala sökningen av Asadpour et al. [2012] och tillhandahålla en ny analys som gör att vi avsevärt kan förbättra gränsen på sin körtid: från 2 O(n) till n O(log n). Våra tekniker har också den intressanta egenskapen att även om vi använder den ganska komplexa konfiguration LP i analysen, vi aldrig faktiskt lösa det och därför den resulterande algoritmen är rent kombinatoriska. Lukáš Poláček och Ola Svensson. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Kvasi-polynomiell lokal sökning efter begränsad maximal-min rättvis fördelning.
Senare visades det i REF att den lokala sökningen kan göras på n O(log n) tid.
Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}