Det är ABSTRACT. Ett av de viktigaste öppna problemen i maskin schemaläggning är problemet med att schemalägga en uppsättning jobb på orelaterade maskiner för att minimera makespan. Den mest kända approximationsalgoritmen för detta problem garanterar en approximationsfaktor på 2. Det är känt att det är N P-hård till ungefärlig med ett bättre förhållande än 3/2. Att överbrygga denna klyfta har varit öppet i över 20 år. De mest kända approximationsfaktorerna uppnås med LP-baserade algoritmer. Den starkaste kända linjära programformuleringen för problemet är konfigurations-LP. Vi visar att konfiguration-LP har en integrality gap på 2 även för specialfall av orelaterad grafbalansering, där varje jobb kan tilldelas högst två maskiner. I synnerhet innebär vårt resultat att en stor familj av nedskärningar inte bidrar till att minska integrality gapet i den kanoniska uppdrag-LP. Vi presenterar också fall av problemet som kan approximeras med en bättre faktor än 2. De utgör värdefulla insikter för att bygga en N P - hårdhet minskning som förbättrar den kända nedre gränsen. Nyligen studerade Svensson [22] det begränsade uppdragsfallet, där varje jobb endast kan tilldelas en viss uppsättning maskiner på vilka det har samma handläggningstid. Han visar att i denna inställning konfiguration-LP har en integrality gap på 33/17  och 1.94. Vårt resultat innebär därför att det icke-närstående grafbalanseringsärendet är betydligt mer komplicerat än det begränsade uppdragsärendet. Sedan vänder vi oss till en annan objektiv funktion: att maximera den minsta maskinbelastningen. För det fall att varje jobb kan tilldelas på de flesta två maskiner ger vi en rent kombinatoriell 2- tillnärmning algoritm som är bäst möjligt, om inte P = N P. Detta förbättrar på beräkning kostsam LP-baserad (2 + ε)-tillnärmning algoritm av Chakrabarty et al. [6]...............................................
Verschae och Wiese REF visade att konfigurationen-LP har integrality gap av 2, även om varje jobb kan tilldelas endast två maskiner.
On the Configuration-LP for Scheduling on Unrelated Machines
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}