近似算法

內(nèi)容概要

本書系統(tǒng)總結(jié)了到本世紀(jì)初為止近似算法領(lǐng)域的成果，重點關(guān)注近似算法的設(shè)計與分析，介紹了這個領(lǐng)域中最重要的問題以及所使用的基本方法和思想。全書分為三部分：第一部分使用不同的算法設(shè)計技巧給出了下述優(yōu)化問題的組合近似算法：集合覆蓋、施泰納樹和旅行商、多向割和k-割、k-中心、反饋頂點集、最短超字符串、背包、裝箱問題、最小時間跨度排序、歐幾里得旅行商等。第二部分介紹基于線性規(guī)劃的近似算法。第三部分包括四個主題：在一個格中找一個最短向量、計數(shù)問題的可近似性、基于PCP定理的近似困難性以及未解決的問題等，這些問題都是近似算法領(lǐng)域中的前沿研究內(nèi)容。    本書可作為計算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)、運籌學(xué)、信息科學(xué)與網(wǎng)絡(luò)工程、物流與交通運輸、管理科學(xué)與工程、生命科學(xué)、電子科學(xué)與技術(shù)等學(xué)科專業(yè)的研究生及高年級本科生的教學(xué)用書，對相關(guān)領(lǐng)域的科學(xué)研究人員也具有參考價值。

作者簡介

Viiay V.Vazirani，佐治亞理工學(xué)院計算學(xué)院教授，加州大學(xué)伯克利分校McKay客座教授，1979年于麻省理工學(xué)院獲得學(xué)士學(xué)位，1983年于加州大學(xué)伯克利分校獲得博士學(xué)位。研究興趣包括數(shù)理經(jīng)濟(jì)學(xué)和對策論中的算法問題、有效精確算法和近似算法的設(shè)計、計算復(fù)雜性理論等。發(fā)表論文120余篇，出版圖書兩本，獲得多項基金資助。2005年當(dāng)選為美國計算機(jī)協(xié)會院士。

書籍目錄

1  引言第一部分  組合算法2  集合覆蓋3  施泰納樹和旅行商4  多向割和k-割5  k-中心6  反饋頂點集7  最短超字符串8  背包9  裝箱問題10  最小時間跨度排序11  歐幾里得旅行商第二部分  基于線性規(guī)劃的算法12  線性規(guī)劃對偶介紹13  用對偶擬合分析集合覆蓋14  舍入應(yīng)用于集合覆蓋15  對集合覆蓋使用原始對偶模式16  最大可滿足性17  無關(guān)平行機(jī)排序18  樹的多割和樹的整數(shù)多商品流19  多向割20  一般圖的多割21  最稀疏割22  施泰納森林23  施泰納網(wǎng)絡(luò)24  設(shè)施定位25  k-中位點26  半定規(guī)劃第三部分  其他主題27  最短向量28  計數(shù)問題29  近似困難性30  未解決的問題附錄A  為算法設(shè)計者概述復(fù)雜性理論B  概率論的基本事實參考文獻(xiàn)問題索引主題索引

編輯推薦

　　《近似算法》涵蓋了獲取難解組合最優(yōu)化問題和計數(shù)問題的近似解的主要理論方法。它包括簡潔優(yōu)雅的組合理論，有用又有趣的算法以及組合問題所固有復(fù)雜性的深入結(jié)果。講解清晰透徹，練習(xí)選取精當(dāng)，《近似算法》必將被所有數(shù)學(xué)和算法研究者所接受并喜愛?！　　督扑惴ā逢P(guān)注近似算法這一重要且適時的主題，寫作上乘，內(nèi)容全面。信廣大讀者無論是將其用作近似性的入門教材，還是作為近似算法諸多問題的參考資料，都會發(fā)現(xiàn)《近似算法》極為有用。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    近似算法 PDF格式下載

---