Ett av de klassiska resultaten i schemaläggning teori är 2- approximation algoritm av Lenstra, Shmoys, och Tardos för problemet med schemaläggning jobb för att minimera makepan på orelaterade maskiner, dvs jobb j kräver tid pij om bearbetas på maskin i. Mer än två decennier efter dess införande är det fortfarande algoritmen för valet även i den begränsade modellen där bearbetningstider är av formen pij  och {pj, ∞}. Detta problem, även känt som problemet med begränsade uppdrag, är NP-hård på att approximera inom en faktor mindre än 1,5 som också är den mest kända lägre gränsen för den allmänna versionen. Vårt huvudresultat är en polynomalgoritm som uppskattar den optimala makepanen av det begränsade tilldelningsproblemet inom en faktor 33/17+  och 1.9412+, där > 0 är en godtyckligt liten konstant. Resultatet erhålls genom att övre avgränsa integrality gap av en viss stark linjär program, känd som konfiguration LP, som tidigare framgångsrikt användes för den relaterade Santa Claus problem. Liknar den starkaste analysen för det problemet våra bevis bygger på en lokal sök algoritm som så småningom kommer att hitta en tidsplan för den nämnda approximation garanti, men är inte känd för att konvergera i polynom tid.
För det begränsade uppdragsfallet, dvs. varje jobb har en fast bearbetningstid och en uppsättning maskiner där man kan tilldela det till, ger Svensson REF en polynomal algoritm som uppskattar den optimala makepan upp till en faktor på 33/17 +  på 1 9412 +.
Santa Claus schedules jobs on unrelated machines
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}