《近似算法的设计与分析》是由高等教育出版社出版的一本关于近似算法方面的书籍，作者是堵丁柱，主要介绍了关于近似算法、设计、分析方面的知识内容，目前在近似算法类书籍综合评分为：8.3分。
书籍介绍
近似算法是解决难解的组成提升难题的1个十分关键和最好的办法。它能够在多项式时间内求取难题的1个解，并使其总体目标函数值与*解的总体目标函数值比例不超出1个常数。这书将根据很多具备象征性的组成提升难题，详细介绍近似算法设计方案和剖析中的几种关键方式 ：贪婪算法、限定方式 和松驰方式 ；所探讨的难题来自不一样的科学研究和主要用途，主要包括网络通信设计方案，网络光纤，无线网络自组织互联网和传感器网络，生物信息学，社会网络，工业工程和管理信息系统等。除此之外，这书还将详细介绍相关组成提升难题不能类似性的某些基础結果。这书的每章节后边都装有有关內容的练习题和历史时间注记。
《近似算法的设计与分析》可做为电子信息科学和运筹学技术专业低年级本科毕业和硕士研究生的近似算法课程内容的教材内容，也可以做为有关科学研究行业科技人员的教材。
目录
- 第一章 引言
- 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-不可近似性
- 习题
- 历史注记
- 参考文献
- 名词索引(汉英对照)
