【文件属性】:
文件名称: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)
网友评论
- 可能需要下一个DjVu的浏览工具
- 不错的算法书!
- 非常好的书,在图书馆找不到了
- 经典好书,感谢分享!
- 内容有些旧了,现在的近似算法有更新的资料。
- 我只参考装箱问题,对写论文有帮助
- 确实是好书····但是要非常非常花精力去看了···
- 内容有些旧了,现在的近似算法有更新的资料。
- 我怎么打不开,花了钱。。。。。。。。。
- 不错的书,稍微有点模糊,谢谢
- 虽然排版上不太好 但是书的内容绝对是顶尖的
- 看到了自己想看的的三着色,不错的东东,满分!!!
- 稍微有点模糊,而且是倒过来的,幸好我只要看一部份,打印出来就可以了。
- 很好的一本书,国内很少能有人写出这样的东东了。
- 从事相关领域研究非常好的参考资料。不足之处是由于原书排版的原因,字体比较小
- 很好,字有些小,不过对于宽屏还好,就是需要旋转一下页面。
- 书很好,字有些小,不过对于宽屏还好,就是需要旋转一下页面。
- 从事相关领域研究非常好的参考资料。不足之处是由于原书排版的原因,字体比较小