中文名: 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