關于占線廣播調度問題的一個下界

徐寅峰　鄭斐峰

摘要：通過研究帶有時限的占線廣播調度問題及其貪婪算法競爭比為5、確定性算法的競爭比下界為2．59，來剖析所有請求均為緊時限的特殊情形，并運用最壞情形分析法分析得出，在任意一個連續中斷的序列中最大中斷比具有逐漸減小的變化特征，進而證明了在所有可能的兩類連續中斷序列中都不可能存在競爭比小于4的確定性算法．由此得出，當請求均為緊時限時，競爭比下界為4．由于緊時限是任意時限的一個特例，從而得出請求為任意時限時的競爭比下界至少為4的結論。

關鍵詞：廣播調度；確定性算法；競爭比；中斷比

中圖分類號：TP393文獻標識碼：A文章編號：025S—987X(2005)12—1291—04