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 Minimize 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 sche