擬陣約束下的分劃問題研究.pdf

1、分劃問題是組合優(yōu)化中的基本問題之一，有許多的組合優(yōu)化問題都可表述為分劃問題，有著廣泛的應(yīng)用，受到眾多學(xué)者的關(guān)注。隨著社會生產(chǎn)的發(fā)展，又不斷地產(chǎn)生一些新問題、新模型。本文回顧了這一領(lǐng)域中的一些典型問題及一些主要結(jié)果，給出了擬陣約束下的瓶頸型分劃問題的提法，并將這些典型的分劃問題統(tǒng)一于擬陣約束下的分劃問題，就其中的一些新模型，研究其近似算法及近似算法的最壞情況界。 全文共分為五章： 第一章介紹本文所需的預(yù)備知識及一些基本概念

2、。在§1.3簡單介紹擬陣的理論，§1.4對分劃問題作扼要回顧，給出了擬陣約束下的瓶頸型分劃問題的提法，并將各種典型分劃問題置于擬陣約束下的分劃問題的框架之下。 第二章討論一般擬陣約束下的分劃問題，針對極小極大問題的目標(biāo)，修正了Edmonds擬陣算法，并分析該算法的最壞情況界。 第三章研究分劃擬陣約束下的瓶頸型分劃問題，考慮到分劃擬陣約束的特點，提出了分層LPT算法，并分析算法的最壞情況界。 第四章繼續(xù)研究分劃擬陣