基本信息

書名:近似算法

定價：49.00元

售價：36.75元,便宜12.25元,摺扣75

作者:(美)瓦齊拉尼,郭效江,方奇誌,農慶琴

齣版社：高等教育齣版社

齣版日期：2010-09-01

ISBN：9787040298635

字數：

頁碼：

版次：1

裝幀：平裝

開本：16開

商品重量：0.640kg

編輯推薦

內容提要

本書係統總結瞭到本世紀初為止近似算法領域的成果，重點關注近似算法的設計與分析，介紹瞭這個領域中重要的問題以及所使用的基本方法和思想。全書分為三部分：部分使用不同的算法設計技巧給齣瞭下述優化問題的組閤近似算法：集閤覆蓋、施泰納樹和旅行商、多嚮割和k-割、k-中心、反饋頂點集、短超字符串、背包、裝箱問題、小時間跨度排序、歐幾裏得旅行商等。第二部分介紹基於綫性規劃的近似算法。第三部分包括四個主題：在一個格中找一個短嚮量、計數問題的可近似性、基於PCP定理的近似睏難性以及未解決的問題等，這些問題都是近似算法領域中的前沿研究內容。
本書可作為計算機科學、應用數學、運籌學、信息科學與網絡工程、物流與交通運輸、管理科學與工程、生命科學、電子科學與技術等學科專業的研究生及高年級本科生的教學用書，對相關領域的科學研究人員也具有參考價值。

目錄

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

作者介紹

Viiay V.Vazirani，佐治亞理工學院計算學院教授，加州大學伯剋利分校McKay客座教授，1979年於麻省理工學院獲得學士學位，1983年於加州大學伯剋利分校獲得博士學位。研究興趣包括數理經濟學和對策論中的算法問題、有效算法和近似算法的設計、計算復雜性理論等。發錶論

文摘

序言