近似算法的設(shè)計(jì)與分析

《近似算法的設(shè)計(jì)與分析》分為五個(gè)部分：首先，在第一部分，即第一章，我們簡明扼要地介紹NP—完全性和近似算法的概念。在第二部分，也就是第二章，我們對貪婪算法進(jìn)行深人的分析，包括以次模函數(shù)為勢函數(shù)的貪婪算法和以非次模函數(shù)為勢函數(shù)的貪婪算法。第三部分包含三章：第三章、第四章和第五章。在這三章中我們討論多種限制方法，其中包含用于處理幾何問題的劃分和斷切方法。第四部分包含第六章、第七章、第八章和第九章。在這四章中我們主要討論松弛方法。在第六章中我們對松弛方法進(jìn)行一般性的討論以后，在緊接著的三章中，討論基于線性和半定規(guī)劃的近似算法設(shè)計(jì)，包括原始對偶方案和與之等價(jià)的局部比值方法。在最后一部分，即第十章，我們介紹應(yīng)用NP—完全性理論的近期成果所取得的各種不可近似性結(jié)果。