近似算法的设计与分析

当前位置:首页 > 计算机网络 > 计算机理论 > 近似算法的设计与分析

出版社:高等教育出版社
出版日期:2011-8
ISBN:9787040319675
作者:堵丁柱,葛可一,胡晓东
页数:426页

内容概要

   堵丁柱,1948年生。中国科学院应用数学研究所运筹学硕士(1981),美国加利福尼亚大学圣巴巴拉分校数学博士(1985),美国伯克利数学科学研究所博士后(1985-1986),美国麻省理工学院助理教授(1986-1987),美国普林斯顿大学访问学者(1990-1991)。曾任美国明尼苏达大学计算机科学系教授,中国科学院应用数学研究所研究员,美国自然科学基金会项目主任,西安交通大学理学院院长。现任美国得克萨斯大学达拉斯分校计算机系教授,西安交通大学理学院名誉院长和高丽大学世界级大学教授。

书籍目录

目录回到顶部↑
《近似算法的设计与分析》
第一章 引言
1.1 “芝麻,开门!”
1.2 近似算法的设计技巧
1.3 启发式算法与近似算法
1.4 计算复杂性的术语
1.5 np-完全问题
1.6 性能比
习题
历史注记
第二章 贪婪策略
2.1 独立系统
2.2 拟阵
2.3 权函数的四边形条件
2.4 次模势函数
2.5 应用
2.6 非次模势函数
习题
历史注记
第三章 限制
.3.1 斯坦纳树和生成树
3.2 k-限制斯坦纳树
3.3 贪婪k-限制斯坦纳树
3.4 最小生成树的应用
3.5 种系进化树同步
习题
历史注记
第四章 划分
4.1 划分与移位
4.2 边界区域
4.3 多层划分
4.4 双重划分
4.5 树划分
习题
历史注记
第五章 断切
5.1 矩形划分
5.2 l-断切
5.3 m-断切
5.4 接口
5.5 四叉树划分与补缀
5.6 两阶段接口
习题
历史注记
第六章 松弛
6.1 有向哈密顿圈和超串
6.2 两阶段贪婪近似算法
6.3 单位圆盘图上连通控制集
6.4 有向图中的强连通控制集
6.5 光纤网络中的多播路由
6.6 关于松弛与限制的附记
习题
历史注记
第七章 线性规划
7.1 基本性质
7.2 单纯形法
7.3 组合舍人
7.4 管输舍人
7.5 迭代舍人
7.6 随机舍人
习题
历史注记
第八章 原始对偶方案与局部比值法
8.1 对偶理论和原始对偶方案
8.2 广义覆盖
8.3 网络设计
8.4 局部比值法
8.5 再论等价性
习题
历史注记
第九章 半定规划
9.1 谱面体
9.2 半定规划
9.3 超平面舍人
9.4 旋转向量
9.5 多元正交舍人
习题
历史注记
第十章 不可近似性
10.1 具有间隙的多一归约
10.2 间隙放大与保持
10.3 apx-完全性
10.4 概率可验证明定理
10.5 (ρin n)-不可近似性
10.6 nc-不可近似性
习题
历史注记
参考文献
名词索引(汉英对照)

编辑推荐

  近似算法是处理难解的组合优化问题的一个非常重要和有效的方法。它可以在多项式时间内求得问题的一个解,并使其目标函数值与最优解的目标函数值之比不超过一个常数。

作者简介

《近似算法的设计与分析》分为五个部分:首先,在第一部分,即第一章,我们简明扼要地介绍NP—完全性和近似算法的概念。在第二部分,也就是第二章,我们对贪婪算法进行深人的分析,包括以次模函数为势函数的贪婪算法和以非次模函数为势函数的贪婪算法。第三部分包含三章:第三章、第四章和第五章。在这三章中我们讨论多种限制方法,其中包含用于处理几何问题的划分和断切方法。第四部分包含第六章、第七章、第八章和第九章。在这四章中我们主要讨论松弛方法。在第六章中我们对松弛方法进行一般性的讨论以后,在紧接着的三章中,讨论基于线性和半定规划的近似算法设计,包括原始对偶方案和与之等价的局部比值方法。在最后一部分,即第十章,我们介绍应用NP—完全性理论的近期成果所取得的各种不可近似性结果。

图书封面


 近似算法的设计与分析下载



发布书评

 
 


精彩短评 (总计14条)

  •     堵丁柱老师的书写的很好,很适合本专业研究生的学习,内容丰富
  •     买来作教材的,知道此书的,还不错啊
  •     这本书一直是很经典的,很多内容值得学习。
  •     嗯。堵老师的书还是挺好的。看看很有帮助。
  •     这本书需要一定的基础,要不就浪费了
  •     内容很经典,值得一看
  •     这个领域不错的入门书。
  •     近似算法的经典教材,本书内容丰富,结构恰当,讲解详细,适合基础较好的人阅读
  •     本书比较好。是一本关于近似算法比较详尽的教材。
  •     还行吧,书的质量可以,
  •     堵丁柱老师是世界知名的数学专家,近似算法是解决NP的工具,本书的数学理论扎实,建议读者要与MIT的《计算理论导引》结合在一起看
  •     近似算法分析!
  •     大致度过。。。看不懂
  •     中国最好的优化学专家的作品,不虚啃读。
 

外国儿童文学,篆刻,百科,生物科学,科普,初中通用,育儿亲子,美容护肤PDF图书下载,。 零度图书网 

零度图书网 @ 2024