文件名称：np难问题近似算法(绝版好书)
文件大小：13.21MB
文件格式：RAR
更新时间：2014-01-11 04:46:01
np难问题近似算法 Dorit S.Hochbaum
这本书在国内已经绝版。目录如下 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 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
【文件预览】：
np难问题近似算法
----Approximation.Algorithms.for.NP-Hard.Problems,.Dorit.S..Hochbaum,.PWS.1997,.WPCBJ.1998.311S.djvu(13.21MB)