Vi föreslår en ny strategi för konkurrensanalys i online-schemaläggningen genom att införa det nya konceptet med konkurrenskraftiga tillnärmningssystem. Ett sådant system konstruerar algoritmiskt en online-algoritm med ett konkurrensförhållande som godtyckligt ligger nära bästa möjliga konkurrensförhållande för alla online-algoritmer. Vi studerar problemet med schemaläggning jobb online för att minimera den viktade summan av slutförandetider på parallella, relaterade, och orelaterade maskiner, och vi härleder både deterministiska och randomiserade algoritmer som är nästan bästa möjliga bland alla online algoritmer i respektive inställningar. Vi generaliserar också våra tekniker till godtyckliga monomiska kostnadsfunktioner och tillämpar dem på makespan-målet. Vår metod bygger på en abstrakt karakterisering av onlinealgoritmer i kombination med olika förenklingar och transformationer. Vi bidrar också med algoritmiska medel för att beräkna det faktiska värdet av bästa möjliga konkurrensförhållande upp till en godtycklig noggrannhet. Detta står i stark kontrast till nästan alla tidigare manuellt erhållna konkurrenskraftsresultat, och framför allt minskar det sökandet efter det optimala konkurrensförhållandet till en fråga som en dator kan svara på. Vi tror att vårt koncept också kan tillämpas på många andra problem och ger ett nytt perspektiv på onlinealgoritmer i allmänhet.
Ett nytt arbete REF ) studerar syntesen av schemaläggare där uppgiften är att minimera den viktade summan av slutförandetider av de släppta uppgifterna.
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}