近似算法

內(nèi)容概要

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

作者簡(jiǎn)介

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

書(shū)籍目錄

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    近似算法 PDF格式下載

---