没有合适的资源?快使用搜索试试~ 我知道了~
近似算法(Approximation algorithms)
5星 · 超过95%的资源 需积分: 41 37 下载量 197 浏览量
2014-10-13
20:09:48
上传
评论 2
收藏 1.55MB PDF 举报
温馨提示
试读
396页
计算机领域基础理论的经典教材,介绍了解决NP问题时常用的近似算法,非常清晰实用的算法入门教材,适用于计算机及其相关学科的本科生、研究生,以及从业者阅读。
资源推荐
资源详情
资源评论
Vijay V. Vazirani
College of Computing
Georgia Institute of Technology
Copyright
c
2001
Approximation Algorithms
Springer
Berlin Heidelberg NewYork
Barcelona Hong Kong
London Milan Paris
Singapore Tokyo
To my parents
Preface
Although this may seem a paradox, all exact
science is dominated by the idea of approximation.
Bertrand Russell (1872–1970)
Most natural optimization problems, including those arising in important
application areas, are NP-hard. Therefore, under the widely believed con-
jecture that P = NP, their exact solution is prohibitively time consuming.
Charting the landscape of approximability of these problems, via polynomial
time algorithms, therefore becomes a compelling subject of scientific inquiry
in computer science and mathematics. This book presents the theory of ap-
proximation algorithms as it stands today. It is reasonable to expect the
picture to change with time.
The book is divided into three parts. In Part I we cover a combinato-
rial algorithms for a number of important problems, using a wide variety
of algorithm design techniques. The latter may give Part I a non-cohesive
appearance. However, this is to be expected – nature is very rich, and we
cannot expect a few tricks to help solve the diverse collection of NP-hard
problems. Indeed, in this part, we have purposely refrained from tightly cat-
egorizing algorithmic techniques so as not to trivialize matters. Instead, we
have attempted to capture, as accurately as possible, the individual character
of each problem, and point out connections between problems and algorithms
for solving them.
In Part II, we present linear programming based algorithms. These are
categorized under two fundamental techniques: rounding and the primal–
dual schema. But once again, the exact approximation guarantee obtainable
depends on the specific LP-relaxation used, and there is no fixed recipe for
discovering good relaxations, just as there is no fixed recipe for proving a the-
orem in mathematics (readers familiar with complexity theory will recognize
this as the philosophical point behind the P = NP question).
Part III covers four important topics. The first is the problem of finding
a shortest vector in a lattice which, for several reasons, deserves individual
treatment (see Chapter 27).
The second topic is the approximability of counting, as opposed to
optimization, problems (counting the number of solutions to a given in-
stance). The counting versions of all known NP-complete problems are #P-
complete
1
. Interestingly enough, other than a handful of exceptions, this is
true of problems in P as well. An impressive theory has been built for ob-
1
However, there is no theorem to this effect yet.
剩余395页未读,继续阅读
资源评论
- glbupt2019-04-08很清晰,有参考性,就是8个积分太贵了
baiyanya
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- apk.tw_LineLite_v8a_v.2.17.1_sign.apk
- Elasticsearch实战:构建高效搜索系统的秘诀.zip
- HTML+CSS+JS网页设计:从入门到精通.zip
- 数据库课程设计:从理论到实践的全面指南.zip
- Python闭包:深入理解与应用场景解析.zip
- Win64OpenSSL-3-3-0.exe
- 课高分程设计-基于C++实现的民航飞行与地图简易管理系统-南京航空航天大学
- 航天器遥测数据故障检测系统python源码+文档说明+数据库(课程设计)
- 北京航空航天大学操作系统课设+ppt+实验报告
- 基于Vue+Echarts实现风力发电机中传感器的数据展示监控可视化系统+源代码+文档说明(高分课程设计)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功