近似算法

图书标准信息

• 作者 瓦齐拉尼 著；郭效江、方奇志、农庆琴 译
• 出版社 高等教育出版社
• 出版时间 2010-09
• 版次 1
• ISBN 9787040298635
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 3636页
• 字数 500千字
• 正文语种 简体中文

【内容简介】

《近似算法》系统总结了到本世纪初为止近似算法领域的成果，重点关注近似算法的设计与分析，介绍了这个领域中最重要的问题以及所使用的基本方法和思想。全书分为三部分：第一部分使用不同的算法设计技巧给出了下述优化问题的组合近似算法：集合覆盖、施泰纳树和旅行商、多向割和k-割、k-中心、反馈顶点集、最短超字符串、背包、装箱问题、最小时间跨度排序、欧几里得旅行商等。第二部分介绍基于线性规划的近似算法。第三部分包括四个主题：在一个格中找一个最短向量、计数问题的可近似性、基于PCP定理的近似困难性以及未解决的问题等，这些问题都是近似算法领域中的前沿研究内容。
《近似算法》可作为计算机科学、应用数学、运筹学、信息科学与网络工程、物流与交通运输、管理科学与工程、生命科学、电子科学与技术等学科专业的研究生及高年级本科生的教学用书，对相关领域的科学研究人员也具有参考价值。

【作者简介】

ViiayV.Vazirani，佐治亚理工学院计算学院教授，加州大学伯克利分校McKay客座教授，1979年于麻省理工学院获得学士学位，1983年于加州大学伯克利分校获得博士学位。研究兴趣包括数理经济学和对策论中的算法问题、有效精确算法和近似算法的设计、计算复杂性理论等。发表论文120余篇，出版图书两本，获得多项基金资助。2005年当选为美国计算机协会院士。

【目录】

1引言
第一部分组合算法
2集合覆盖
3施泰纳树和旅行商
4多向割和k-割
5k-中心
6反馈顶点集
7最短超字符串
8背包
9装箱问题
10最小时间跨度排序
11欧几里得旅行商

第二部分基于线性规划的算法
12线性规划对偶介绍
13用对偶拟合分析集合覆盖
14舍入应用于集合覆盖
15对集合覆盖使用原始对偶模式
16最大可满足性
17无关平行机排序
18树的多割和树的整数多商品流
19多向割
20一般图的多割
21最稀疏割
22施泰纳森林
23施泰纳网络
24设施定位
25k-中位点
26半定规划

第三部分其他主题
27最短向量
28计数问题
29近似困难性
30未解决的问题

附录
A为算法设计者概述复杂性理论
B概率论的基本事实
参考文献
问题索引
主题索引