近似算法

出版时间：2010-9  出版社：高等教育出版社  作者：瓦齐拉尼  页数：3636  
Tag标签：无  

内容概要

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

作者简介

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

书籍目录

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  概率论的基本事实参考文献问题索引主题索引

编辑推荐

　　《近似算法》涵盖了获取难解组合最优化问题和计数问题的近似解的主要理论方法。它包括简洁优雅的组合理论，有用又有趣的算法以及组合问题所固有复杂性的深入结果。讲解清晰透彻，练习选取精当，《近似算法》必将被所有数学和算法研究者所接受并喜爱。　　《近似算法》关注近似算法这一重要且适时的主题，写作上乘，内容全面。信广大读者无论是将其用作近似性的入门教材，还是作为近似算法诸多问题的参考资料，都会发现《近似算法》极为有用。

用户评论 (总计6条)

•   内容覆盖面宽，较前沿
•   不错不错。。。哈哈
•   you must buy it.
•   虽然还没仔细看 不过应该还不错的
•   还算满意。其实如果看原版，更好。
•   我买过随机算法，一个出版社的，那组翻译人员是学鹦鹉的吧，我*，翻译的有错的地方不说（很多错误），竟然连语序都不变，这是随机算法
  
  近似算法，我刚开始看，不过也一般，要不是老师让我们假期讲这破烂子东西，我是不过买的，真正想学的话，得花出时间看，这不是上课那点时间能学懂的，建议大家看英文原版，既然你都搜索近似算法这类书籍了，证明你学历不低了，看看原版吧，比translate in China 好上百倍！