若干算法的復雜性分析問題研究.pdf

1、該文在算法的復雜性分析研究領(lǐng)域所做的研究工作涉及以下三個方面:算法的復雜性平滑分析、在線調(diào)度算法的競爭比分析和最小擊中集問題的隨機近似算法的設(shè)計與分析.主要工作陳述如下:(1)該文在高斯隨機擾動模型下,對矩陣條件數(shù)和運行高斯算法所需機器精度位數(shù)的平滑分析做進一步的研究,提出并證明了兩個不等式,簡化了Sankar等人關(guān)于矩陣條件數(shù)平滑分析的結(jié)果,部分解決了Sankar等人提出的有關(guān)改進矩陣條件數(shù)平滑分析結(jié)果的猜想.在此基礎(chǔ)上降低了Sank

2、ar等人關(guān)于運行高斯算法所需機器精度位數(shù)的平滑復雜性,并通過實驗進行比較說明.(2)該文在0-保留高斯隨機擾動模型下,進一步研究了對稱矩陣條件數(shù)及運行高斯算法所需的機器精度位數(shù)的平滑分析.(3)該文在離散算法的復雜性平滑分析方面進行了研究,并從實際的應(yīng)用背景出發(fā),提出一個隨機擾動模型(在該文中簡稱TSSP模型),用于對算法的輸入實例是一個元素序列而算法的復雜性主要取決于其輸入實例中的元素排列順序這樣一類離散算法的復雜性平滑分析.(4)該

3、文研究多處理機環(huán)境下的作業(yè)調(diào)度問題.在線作業(yè)調(diào)度算法的競爭比分析中,作業(yè)的流動時間及作業(yè)的延遲比是用來度量調(diào)度算法性能優(yōu)劣的兩個主要指標.作業(yè)的延遲比是指作業(yè)從進入系統(tǒng)到完成所需要的時間與作業(yè)的執(zhí)行時間之比.作業(yè)的平均延遲比是作業(yè)的延遲比總和與作業(yè)數(shù)之比值(等價地,作業(yè)的延遲比總和).作業(yè)的平均延遲比能更直觀更合理地反映在線調(diào)度算法性能的優(yōu)劣.該文證明了Avrahami等人提出的在線調(diào)度算法IMD對于最小化作業(yè)平均延遲比具有常數(shù)競爭比.

4、(5)該文研究隨機擾動模型M(m,n,k)產(chǎn)生的隨機k-SAT實例的若干性質(zhì)及子句密度與可滿足性之間的關(guān)系,證明了當子句密度足夠大時,隨機k-SAT實例的不可滿足性判定可以歸結(jié)到最小k-Hitting Sets問題的求解.(6)Franco等人在文[62]中給出基于平均度數(shù)的最小3-Hitting Sets貪心算法,并給出算法返回擊中集規(guī)模的上界.該文將此算法推廣成為求解最小k-Hitting Sets的貪心算法HGREEDY1(A,C