下载 >  开发技术 >  其它 > np难问题近似算法(绝版好书)

np难问题近似算法(绝版好书) 评分:

这本书在国内已经绝版。目录如下 Introduction Dorit S. Hochbaum 0.1 What can approximation algorithms do for you: an illustrative example 0.2 Fundamentals and concepts 0.3 Objectives and organization of this book 0.4 Acknowledgments I Approximation Algorithms for Scheduling Leslie A. Hall 1.1 Introduction 1.2 Sequencing with Release Dates to Minimiz e Lateness 1.2.1 Jacksons rule 1.2.2 A simple 3/2-approximation algorithm 1.2.3 A polynomial approximation scheme 1.2.4 Precedence constraints and preprocessing 1.3 Identical parallel machines: beyond list scheduling 1.3.1 P|rj,prec|Lmax:: list scheduling revisited 1.3.2 The LPT rule for P‖Cmax 1.3.3 The LPT rule for P|rj|Cmax 1.3.4 Other results for identical parallel machines 1.4 Unrelated parallel machines 1.4.1 A 2-approximation algorithm based on linear programming 1.4.2 An approximation algorithm for minimizing cost and makespan 1.4.3 A related result from network scheduling 1.5 Shop scheduling 1.5.1 A greedy 2-approximation algorithm for open shops 1.5.2 An algorithm with an absolute error bound 1.5.3 A 2 E -approximation algorithm for fixed job and flow shops 1.5.4 The general job shop: unit-time operations 1.6 Lower bounds on approximation for makespan scheduling 1.6.1 Identical parallel machines and precedence constraints 1.6.2 Unrelated parallel machines 1.6.3 Shop scheduling 1.7 Min-sum Objectives 1.7.1 Sequencing with release dates to minimize sum of completion times 1.7.2 Sequencing with precedence constraints 1.7.3 Unrelated parallel machines 1.8 Final remarks 2 Approximation Algorithms for Bin Packing: A Survey E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson 2.1 Introduction 2.2 Worst-case analysis 2.2.1 Next fit 2.2.2 First fit 2.2.3 Best fit, worst fit, and almost any fit algorithms 2.2.4 Bounded-space online algorithms 2.2.5 Arbitrary online algorithms 2.2.6 Semi-online algorithms 2.2.7 First fit decreasing and best fit decreasing 2.2.8 Other simple offline algorithms 2.2.9 Special-case optimality, approximation schemes, and asymptotically optimal algorithms 2.2.10 Other worst-case questions 2.3 Average-case analysis 2.3.1 Bounded-space online algorithms 2.3.2 Arbitrary online algorithms 2.3.3 Offiine algorithms 2.3.4 Other average-case questions 2.4 Conclusion Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems Dorit S. Hachbaum 3.1 Introduction 3.1.1 Definitions, formulations and applications 3.1.2 Lower bounds on approximations 3.1.3 Overview of chapter 3.2 The greedy algorithm for the set cover problem 3.3 The LP-algorithm for set cover 3.4 The feasible dual approach 3.5 Using other relaxations to derive dual feasible solutions 3.6 Approximating the multicoverproblem 3.7 The optimal dual approach for the vertex cover and independent set problems: preprocessing 3.7.1 The complexity of the LP-relaxation of vertex cover and independent set 3.7.2 Easily colorable graphs 3.7.3 A greedy algorithm for independent set in unweighted graphs 3.7.4 A local-ratio theorem and subgraph removal 3.7.5 Additional algorithms without preprocessing 3.7.6 Summary of approximations for vertex cover and independent set 3.8 Integer programming with two variables per inequality 3.8.1 The half integrality and the linear programming relaxation 3.8.2 Computing all approximate solution 3.8.3 The equivalence of IP2 to 2-SAT and 2-SAT to vertex cover 3.8.4 Properties of binary integer programs 3.8.5 Dual feasible solutions for IP2 3.9 The maximum coverage problem and the greedy 3.9.1 Tile greedy approach 3.9.2 Applications of the maxinmum coverage problem 4 The Primal-Dual Methud for Approximation Algorithms and Its Applicatiun to Network Design Problems Michel X. Goemans and David P. Williamson 4.1 Introduction 4.2 The classical primal-dual method 4.3 Thc primal-dual method Im approximation algorithms 4.4 A model of network design problems 4.4.1 0-I functions 4.5 Downwards monotone functions 4.5.1 The edge-covering problem 4.5.2 Lower capacitated partitioning problems 4.5.3 Location-design and location-routing problems 4.5.4 Proof of Theorems 4.5 and 4.6 4.6 0-1 proper functions 4.6.1 The generalized Sterner tree problem 4.6.2 The T-join problem 4.6.3 The minimum-weight perfect matching problem 4.6.4 Point-to-point connection problems 4.6.5 Exact partitioning problems 4.7 General proper functions 4.8 Extensions 4.8.1 Mininmm multicut in trees 4.8.2 The prize-collecting problems 4.8.3 Vertex connectivity problems 4.9 Conclusions 5 Cut Problems and Their Application to Divide-and-Conquer David B. Shmoys 5.1 Introduction 5.2 Minimum multicuts and maximum multicommodity flow 5.2.1 Multicuts, maximum multicommodity flow, and a weak duality theorem 5.2.2 Fractional multicuts, pipe systems, and a strong duality theorem 5.2.3 Solving the linear programs 5.2.4 Finding a good multicut 5.3 Sparsest cuts and maximum concurrent flow 5.3.1 The sparsest cut problem 5.3.2 Reducing the sparsest cut problem to the minimum multicut problem 5.3.3 Embeddings and the sparsest cut problem 5.3.4 Finding a good embedding 5.3.5 The maximum concurrent flow problem 5.4 Minimum feedback arc sets and related problems 5.4.1 An LP-based approximation algorithm 5.4.2 Analyzing the algorithm Feedback 5.4.3 Finding a good partition 5.5 Finding balanced cuts and other applications 5.5.1 Finding balanced cuts 5.5.2 Applications of balanced cut theorems 5.6 Conclusions Approximation Algorithms for Finding Highly Connected Suhgraphs Samir KhulJer 6.1 Introduction 6.1.1 Outline of chapter and techniques 6.2 Edge-connectivity problems 6.2.1 Weighted edge-connectivity 6.2.2 Unweighted edge-connectivity 6.3 Vertex-connectivity problems 6.3.1 Weighted vertex-connectivity 6.3.2 Unweighted vertex-connectivity 6.4 Strong-connectivity problems 6.4.1 Polynomial time approximation algorithms 6.4.2 Nearly linear-time implementation 6.5 Connectivity augmentation 6.5.1 increasing edge connectivity from I to 2 6.5.2 Increasing vertex connectivity from I to 2 6.5.3 Increasing edge-connectivity to 3. Algorithms for Finding Low Degree Structures Balaji Raghavachari 7.1 Introduction 7.2 Toughness and degree 7.3 Matchings and MDST 7.4 MDST within one of optimal 7.4.1 Witness sets 7.4.2 The △* 1 algorithm 7.4.3 Performance analysis 7.5 Local search techniques 7.5.1 MDST problem 7.5.2 Constrained forest problems 7.5.3 Two-connected subgraphs 7.6 Problems with edge weights - points in Euclidean spaces 7.7 Open problems 8 Approximation Algorithms for Geometric Problems Marshall Bern and David Eppstein 8.1 Introduction 8.1.1 Overview of topics 8.1.2 Special nature of geometric problems 8.2 Traveling salesman problem 8.2.1 Christofides algorithm 8.2.2 Heuristics 8.2.3 TSP with neighborhoods 8.3 Steiner tree problem 8.3.1 Steiner ratios 8.3.2 Better approximations 8.4 Minimum weight triangulation 8.4.1 Triangulation without Steiner points 8.4.2 Steiner triangulation 8.5 Clustering 8.5.1 Minmax k-clustering 8.5.2 k-minimum spanning tree 8.6 Separation problems 8.6.1 Polygon separation 8.6.2 Polyhedron separation 8.6.3 Point set separation 8.7 Odds and ends 8.7.1 Covering orthogonal polygons by rectangles 8.7.2 Packing squares with fixed comers 8.7.3 Largest congruent subsets 8.7.4 Polygon bisection 8.7.5 Graph embedding 8.7.6 Low-degree spanning trees 8.7.7 Shortest paths in space 8.7.8 Longest subgraph problems 8.8 Conclusions 9 Various Notions of Approximations: Good, Better, Best, and More Dorit S. Hochbaum 9.1 Introduction 9.1.1 Overview of chapter 9.2 Good: fixed constant approximations 9.2.1 The weighted undirected vertex feedback set problem 9.2.2 The shortest superstring problem 9.2.3 How maximization versus minimization affects approximations 9.3 Better: approximation schemes 9.3.1 A fully polynomial approximation scheme for the knapsack problem 9.3.2 The minimum makespan and the technique of dual approximations 9.3.3 Geometric packing and covering--the shifting technique 9.4 Best: unless NP = P 9.4.1 The k-center problem 9.4.2 A powerful approximation technique for bottleneck problems 9.4.3 Best possible parallel approximation algorithms 9.5 Better than best 9.5.1 A FPAS for bin packing 9.5.2 A 9/8-approximation algorithm for ~dge coloring of multigraphs and beyond 9.6 Wonderful: within one unit of optimum 10 Hardness of Approximations San jeer Arora and Carsten Lund 10.1 Introduction 10.2 How to prove inapproximability results 10.2.1 The canonical problems 10.2.2 Inapproximability results for the canonical problems 10.2.3 Gap preserving reductions 10.3 Inapproximability results for problems in class I 10.3.1 Max-SNP 10.4 Inapproximability results for problems in class II 10.4.1 SETCOVER 10.5 Inapproximability results lor problems in class 111 10.5.1 LABELCOVER maximization version ,. 10.5.2 LABELCOVER mtn version 10.5.3 Nearest lattice vector problem 10.6 Inapproximability results for problems in class IV 10.6.1 CLIQUE 10.6.2 COLORING 10.7 Inapproximability results at a glance 10.7.1 How to prove other hardness results: a case study 10.8 prohabilistically checkable proofs and inapproximability 10.8.1 The PCP theorem 10.8.2 Connection to inapproximability of MAX-3SAT 10.8.3 Where the gap comes from 10.9 Open problems 10.10 Chapter notes 11 Randomized Approximation Algorithms in Combinatorial Optimization Rajeev Motwani, Joseph Seffi Naor, and Prabhakar Raghavan 11.1 Introduction 11.2 Rounding linear programs 11.2.1 The integer multicommodity flow problem 11.2.2 Covering and packing problems 11.2.3 The maximum satisfiability problem 11.2.4 Related work 11.3 Semidefinite programming 11.3.1 The maximum cut problem 11.3.2 The graph coloring problem 11.4 Concluding remarks 11.4.1 Derandomizafion and parallelization 11.4.2 Computational experience 11.4.3 Open problems 12 The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration Mark Jerrum and Alistair Sinclair 12.1 Introduction 12.2 An illustrative example 12.3 Two techniques for bounding the mixing time 12.3.1 Canonical paths 12.3.2 Conductance 12.4 A more complex example: monomer-dimer systems 12.5 More applications 12.5.1 The permanent 12.5.2 Volume of convex bodies 12.5.3 Statistical physics 12.5.4 Matroid bases: an open problem 12.6 The Metropolis algorithm and simulated annealing Appendix 13 Online Computation Sandy Irani and Anna R. Karlin 13.1 Introduction 13.2 Three examples of competitive analysis 13.2.1 Paging 13.2.2 The k-server problem 13.2.3 Metrical task systems 13.3 Theoretical underpinnings: deterministic algorithms 13.3.1 Lower bounds 13.3.2 Design principles 13.3.3 Bounding competitiveness 13.4 Theoretical underpinnings: randomized algorithms 13.4.1 Example: paging 13.4.2 Lower bounds 13.4.3 The relationships between the adversaries 13.5 The k-server problem revisited 13.5.1 History. 13.5.2 Notation and properties of work functions. 13.5.3 The work function algorithm WFA 13.5.4 Proof of 2k - 1 -competitiveness 13.5.5 The duality lemma 13.5.6 The potential function 13.5.7 Quasi-convexity and the duality lemma 13.6 Online load balancing and virtual circuit routing 13.6.1 Load balancing on unrelated machines 13.6.2 Online virtual circuit routing 13.6.3 Recent results 13.7 Variants of competitive analysis 13.8 Conclusions and directions for future research Glossary of Problems Index
...展开详情收缩
分享
收藏 (3) 举报

评论 共22条

u010625071 不错的算法书!
2017-11-22
回复
foxlu2000 非常好的书,在图书馆找不到了
2016-02-02
回复
guangzhou_wuhan 经典好书,感谢分享!
2015-12-18
回复
li496070899 内容有些旧了,现在的近似算法有更新的资料。
2015-07-13
回复
beiger 有些模糊,但内容很好
2015-03-14
回复
fengyejushi 十分好的东西,有了它学起来就方便了
2014-11-01
回复
qiyuan19901990 不错,挺有用的。
2014-10-09
回复
mmilklemon 字太小了。。。参考了装箱这一部分,还不错。
2014-09-07
回复
tianya890601 内容很好,就是稍微模糊了些
2014-06-22
回复
ds1204 我只参考装箱问题,对写论文有帮助
2013-10-09
回复
算法中的P问题、NP问题、NP完全问题和NP难问题
P问题、NP问题、NP完全问题和NP难问题
科普,什么是“NP难”的问题。专业的解释俺看不懂。这个文章里面举了几个例子,俺一下就明白了。
对于“NP难问题”的理解
时间复杂度与NP/NP难/NP完全问题的最简单理解法
为什么说旅行商问题是NP Hard的?
p问题、np问题、npc问题、np难问题的理解(纯属个人见解)
NP难问题求解综述
P问题、NP难问题详解

P问题、NP难问题详解 总结: 定义:同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。 证明:先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它

立即下载
P问题、NP问题、NP完全问题和NP难问题概念梳理
NP-难问题--整数规划教程

整数规划教程,整数规划是线性规划的一个分支,属NP-难问题

立即下载
为什么说01背包问题是NP完全问题,以及NPCNPH的区分。
NP-Hard问题浅谈
P问题、NP问题、NPC问题、NP-hard问题详解
P、NP、NPC和NP-Hard相关概念的图形和解释
[总结]算法中的P问题、NP问题、NP完全问题和NP难问题
NP-hard问题概念理解
NP、NP-完全、NP-难问题
最简单的NP-hard问题
关于P问题,NP问题,NP难问题的介绍

热点文章

img

spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
点击完成任务获取下载码
输入下载码
为了良好体验,不建议使用迅雷下载
img

np难问题近似算法(绝版好书)

会员到期时间: 剩余下载个数: 剩余C币: 剩余积分:0
为了良好体验,不建议使用迅雷下载
VIP下载
您今日下载次数已达上限(为了良好下载体验及使用,每位用户24小时之内最多可下载20个资源)

积分不足!

资源所需积分/C币 当前拥有积分
您可以选择
开通VIP
4000万
程序员的必选
600万
绿色安全资源
现在开通
立省522元
或者
购买C币兑换积分 C币抽奖
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
为了良好体验,不建议使用迅雷下载
确认下载
img

资源所需积分/C币 当前拥有积分 当前拥有C币
2 0 0
为了良好体验,不建议使用迅雷下载
VIP和C币套餐优惠
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
您的积分不足,将扣除 10 C币
为了良好体验,不建议使用迅雷下载
确认下载
下载
您还未下载过该资源
无法举报自己的资源

兑换成功

你当前的下载分为234开始下载资源
你还不是VIP会员
开通VIP会员权限,免积分下载
立即开通

你下载资源过于频繁,请输入验证码

您因违反CSDN下载频道规则而被锁定帐户,如有疑问,请联络:webmaster@csdn.net!

举报

  • 举报人:
  • 被举报人:
  • *类型:
    • *投诉人姓名:
    • *投诉人联系方式:
    • *版权证明:
  • *详细原因: