NP 难解问题的近似算法(Approximation Algorithms for NP-Hard Problems)英文版[DJVU]

游客，本帖隐藏的内容需要积分高于 1 才可浏览，您当前积分为 0

资源信息： 中文名: NP 难解问题的近似算法 原名: Approximation Algorithms for NP-Hard Problems 作者: Hochbaum Ye 图书分类: 软件 资源格式: DJVU 版本: 英文版 出版社: Hochbaum Ye 书号: 750623630 发行时间: 1998年 地区: 大陆 语言: 英文 概述:

djvu 阅读器： http://windjview.sourceforge.net/ 内容简介： 近似算法的引入和发展是为了解决一大类重要的优化问题，人们常常遇到的这类问题是 NP-Hard 问题。 按照 Garey 和 Johnson 的说法：“我没能找到一个有效的算法，但是其他那么多名人同样也没找到！” 如果找不到最优解时，那么合理的做法是牺牲一点最优性而去寻求有效的，好的，可行的近似解 。当然在保证解的有效性时候，其最优性要尽可能的保留。近似算法的模式就是为了寻求这种平衡。 本书就是讨论关于若干类重要 NP-Hard 问题的近似解算法，书中回顾了近几十年来相关的设计技术，及其进展。 内容截图：

目录: 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 Minimize Lateness 1.2.1 Jackson''s 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 I''m'' 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 ... Glossary of Problems Index