Vi överväger att ställa in online beräkning med råd, och studera bin förpackning problem och ett antal schemaläggning problem. Vi visar att det är möjligt, för något av dessa problem, att godtyckligt närma sig ett konkurrensförhållande på 1 med bara ett konstant antal bitar av råd per begäran. För bin förpackningsproblem, ger vi en online-algoritm med råd som är (1 + ε)-konkurrenskraft och använder O 1 ε log 1 ε bitar av råd per begäran. För schemaläggning på m identiska maskiner, med objektiv funktion av någon av makespan, maskintäckning och minimering av lp norm, p > 1, ger vi liknande resultat. Vi ger online-algoritmer med råd som är (1 + ε) konkurrenskraftiga ((1/(1 − ε)) konkurrenskraftiga för maskintäckning) och även använda O 1 ε log 1 ε bitar av råd per begäran. Vi kompletterar våra resultat genom att ge en lägre gräns som visar att för varje online-algoritm med råd ska vara optimal, för någon av ovanstående schemaläggning problem, ett icke-konstant antal (nämligen minst 1 − 2m n log m, där n är antalet jobb och m är antalet maskiner) bitar av råd per begäran behövs.
Renault m.fl. REF presentera en LAAS för Bin Packing problem, och för en familj av schemaläggning problem på m identiska maskiner som innehåller målen att minimera makespan, minimera p norm, och maskintäckning.
Online Algorithms with Advice for Bin Packing and Scheduling Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}