近似算法

內(nèi)容概要

本書系統(tǒng)總結(jié)了到本世紀(jì)初為止近似算法領(lǐng)域的成果，重點(diǎn)關(guān)注近似算法的設(shè)計(jì)與分析，介紹了這個(gè)領(lǐng)域中最重要的問題以及所使用的基本方法和思想。全書分為三部分：第一部分使用不同的算法設(shè)計(jì)技巧給出了下述優(yōu)化問題的組合近似算法：集合覆蓋、施泰納樹和旅行商、多向割和k-割、k-中心、反饋頂點(diǎn)集、最短超字符串、背包、裝箱問題、最小時(shí)間跨度排序、歐幾里得旅行商等。第二部分介紹基于線性規(guī)劃的近似算法。第三部分包括四個(gè)主題：在一個(gè)格中找一個(gè)最短向量、計(jì)數(shù)問題的可近似性、基于PCP定理的近似困難性以及未解決的問題等，這些問題都是近似算法領(lǐng)域中的前沿研究?jī)?nèi)容。    本書可作為計(jì)算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)、運(yùn)籌學(xué)、信息科學(xué)與網(wǎng)絡(luò)工程、物流與交通運(yùn)輸、管理科學(xué)與工程、生命科學(xué)、電子科學(xué)與技術(shù)等學(xué)科專業(yè)的研究生及高年級(jí)本科生的教學(xué)用書，對(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ì)策論中的算法問題、有效精確算法和近似算法的設(shè)計(jì)、計(jì)算復(fù)雜性理論等。發(fā)表論文120余篇，出版圖書兩本，獲得多項(xiàng)基金資助。2005年當(dāng)選為美國計(jì)算機(jī)協(xié)會(huì)院士。

書籍目錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

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

---

    近似算法 PDF格式下載

---