Online algoritmer är ett kännetecken för värsta fall optimering under osäkerhet. Å andra sidan är inputen i praktiken ofta långt ifrån det värsta och har vissa förutsägbara egenskaper. En ny typ av arbete har visat hur man använder maskininlärda förutsägelser för att kringgå starka lägre gränser på konkurrensförhållanden i klassiska online-problem som skiduthyrning och caching. Vi studerar hur prediktiva tekniker kan användas för att bryta igenom värsta fallbarriärer i online schemaläggning. Makespan minimization problem med begränsade uppdrag är ett klassiskt problem i online schemaläggning teori. I värsta fall ger analysen av detta problem lägre gränser för konkurrensförhållandet på nätet. Vi identifierar en robust mängd som kan förutses och sedan användas för att vägleda online-algoritmer för att uppnå bättre prestanda. Våra förutsägelser är kompakta i storlek, har dimension linjär i antalet maskiner, och kan läras med hjälp av standard utanför hyllan metoder. Prestandagarantierna för våra algoritmer beror på exaktheten i förutsägelserna, givet förutsägelser med fel η, visar vi hur man konstruerar O (log η) konkurrenskraftiga deluppdrag. Vi ger sedan en online-algoritm som rundar alla fraktionerade uppdrag i ett integrerat schema. Vår algoritm är O((log log m) 3 )-konkurrenskraftig och vi ger en nästan matchande (log log m) lägre gräns för online avrundningsalgoritmer. 1 Sammantaget ger vi algoritmer som, utrustade med förutsägelser med fel η, uppnå O(log η (logglogg m) 3 ) konkurrenskraftiga nyckeltal, bryta den lägre gränsen även för måttligt korrekta förutsägelser.
Ref studerade problemet med begränsad tilldelning schemaläggning, med förutsägelser om vissa dubbla variabler kopplade till maskinerna, och kunde få en O(log η(log log m) 3 ) kompetitiv algoritm för problemet.
Online Scheduling via Learned Weights
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}