關(guān)于占線廣播調(diào)度問題的一個下界
2005-04-29 00:44:03徐寅峰鄭斐峰
西安交通大學(xué)學(xué)報 2005年12期
徐寅峰 鄭斐峰
摘要：通過研究帶有時限的占線廣播調(diào)度問題及其貪婪算法競爭比為5、確定性算法的競爭比下界為2．59，來剖析所有請求均為緊時限的特殊情形，并運用最壞情形分析法分析得出，在任意一個連續(xù)中斷的序列中最大中斷比具有逐漸減小的變化特征，進而證明了在所有可能的兩類連續(xù)中斷序列中都不可能存在競爭比小于4的確定性算法．由此得出，當請求均為緊時限時，競爭比下界為4．由于緊時限是任意時限的一個特例，從而得出請求為任意時限時的競爭比下界至少為4的結(jié)論。
關(guān)鍵詞：廣播調(diào)度；確定性算法；競爭比；中斷比
中圖分類號：TP393文獻標識碼：A文章編號：025S—987X(2005)12—1291—04
