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

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

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