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

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

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

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

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