Vi överväger online-algoritmer för pull-baserad sändning schemaläggning. I denna inställning finns n sidor av information på en server och förfrågningar om sidor anländer online. När servern betjänar (broadcasts) en sida p, alla utestående förfrågningar om den sidan är nöjda. Vi studerar två relaterade mätvärden, nämligen maximal svarstid (vänttid) och maximal fördröjningsfaktor och deras viktade versioner. Vi får följande resultat i den sämsta online-konkurrensmodellen. • Vi visar att FIFO (first-in first-out) är 2-konkurrenskraftigt även när sidstorlekarna är olika. Tidigare var detta känt endast för unit-size-sidor [10] via ett känsligt argument. Våra bevis skiljer sig från [10] och är kanske mer intuitiva. • Vi ger en online-algoritm för maximal delay-faktor som är O(1/ på 2 )-kompetitiv med (1 +  på)-hastighet för unit-size sidor och med (2 +  på)-hastighet för olika stora sidor. Detta förbättrar algoritmen i [12] som krävs (2 +  på)-hastighet och (4 +  på)-hastighet. Dessutom visar vi att algoritmen och analysen kan utökas för att få samma resultat för maximal viktad svarstid och fördröjningsfaktor. • Vi visar att en naturlig girig algoritm modellerad efter LWF (Longest-Way-First) inte är O(1)-konkurrenskraftig för maximal fördröjningsfaktor med någon konstant hastighet även i inställningen av standard schemaläggning med enhetsstora jobb. Detta kompletterar vår övre gräns och visar betydelsen av kompromissen som gjorts i vår algoritm.
Chekuri Ref fokuserade på schemaläggning för att minimera två relaterade mål: maximal svarstid och maximal fördröjningsfaktor.
Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}