Book Description
Delineating the tremendous growth in this area, the Handbook of Approximation Algorithms and Metaheuristics covers fundamental, theoretical topics as well as advanced, practical applications. It is the first book to comprehensively study both approximation algorithms and metaheuristics. Starting with basic approaches, the handbook presents the methodologies to design and analyze efficient approximation algorithms for a large class of problems, and to establish inapproximability results for another class of problems. It also discusses local search, neural networks, and metaheuristics, as well as multiobjective problems, sensitivity analysis, and stability. After laying this foundation, the book applies the methodologies to classical problems in combinatorial optimization, computational geometry, and graph problems. In addition, it explores large-scale and emerging applications in networks, bioinformatics, VLSI, game theory, and data analysis. Undoubtedly sparking further developments in the field, this handbook provides the essential techniques to apply approximation algorithms and metaheuristics to a wide range of problems in computer science, operations research, computer engineering, and economics. Armed with this information, researchers can design and analyze efficient algorithms to generate near-optimal solutions for a wide range of computational intractable problems.
[目录]
PREFACE BASIC METHODOLOGIES
1、 Introduction, Overview, and Notation
2、 Basic Methodologies and Applications
3、 Restriction Methods
4、 Greedy Methods
5、 Recursive Greedy Methods
6、 Linear Programming
7、 LP Rounding and Extensions
8、 On Analyzing Semidefinite Programming Relaxations of ComplexQuadratic Optimization Problems
9、 Polynomial-Time Approximation Schemes
10、 Rounding, Interval Partitioning, and Separation
11、 Asymptotic Polynomial-Time Approximation Schemes
12、 Randomized Approximation Techniques
13、 Distributed Approximation Algorithms via LP-Duality and Randomization
14、 Empirical Analysis of Randomized Algorithms
15、 Reductions that Preserve Approximability
16、 Differential Ratio Approximation
17、 Hardness of Approximation
LOCAL SEARCH, NEURAL NETWORKS, AND METAHEURISTICS
18、 Local Search
19、 Stochastic Local Search
20、 Very Large-Scale Neighborhood Search: Theory, Algorithms, and Applications
21、 Reactive Search: Machine Learning for Memory-Based Heuristics
22、 Neural Networks
23、 Principles of Tabu Search
24、 Evolutionary Computation
25、 Simulated Annealing
26、 Ant Colony Optimization
27、 Memetic Algorithms
MULTIOBJECTIVE OPTIMIZATION, SENSITIVITY ANALYSIS, AND STABILITY
28、 Approximation in Multiobjective Problems
29、 Stochastic Local Search Algorithms for Multiobjective Combinatorial Optimization: A Review
30、 Sensitivity Analysis in Combinatorial Optimization
31、 Stability of Approximation
TRADITIONAL APPLICATIONS
32、 Performance Guarantees for One-Dimensional Bin Packing
33、 Variants of Classical One-Dimensional Bin Packing
34、 Variable, Sized Bin Packing and Bin Covering
35、 Multidimensional Packing Problems
36、 Practical Algorithms for Two-Dimensional Packing
37、 A Generic Primal-Dual Approximation Algorithm for an Interval Packing and Stabbing Problem
38、 Approximation Algorithms for Facility Dispersion
39、 Greedy Algorithms for Metric Facility Location Problems
40、 Prize-Collecting Traveling Salesman and Related Problems
41、 A Development and Deployment Framework for Distributed Branch and Bound
42、 Approximations for Steiner Minimum Trees
43、 Practical Approximations of Steiner Trees in Uniform Orientation Metrics
44、 Approximation Algorithms for Imprecise Computation Tasks with 0/1 Constraint
45、 Scheduling Malleable Tasks
46、 Vehicle Scheduling Problems in Graphs
47、 Approximation Algorithms and Heuristics for Classical Planning
48、 Generalized Assignment Problem
49、 Probabilistic Greedy Heuristics for Satisfiability Problems
COMPUTATIONAL GEOMETRY AND GRAPH APPLICATIONS
50、 Approximation Algorithms for Some Optimal 2D and 3D Triangulations
51、 Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs
52、 Dilation and Detours in Geometric Networks
53、 The Well-Separated Pair Decomposition and its Applications
54、 Minimum-Edge Length Rectangular Partitions
55、 Partitioning Finite d-Dimensional Integer Grids with Applications
56、 Maximum Planar Subgraph
57、 Edge-Disjoint Paths and Unsplittable Flow
58、 Approximating Minimum-Cost Connectivity Problems
59、 Optimum Communication Spanning Trees
60、 Approximation algorithms for multilevel graph partitioning
61、 Hypergraph partitioning and clustering
62、 Finding most vital edges in a graph
63、 Stochastic local search algorithms for the graph coloring problem
64、 On solving the maximum disjoint paths problem with ant colony optimization
LARG-SCALE AND EMERGING APPLICATIONS
65、 Cost-efficient multicast routing in ad hoc and sensor networks
66、 Approximation algorithm for clustering in ad hoc networks
67、 Topology control problems for wireless ad hoc networks
68、 Geometrical spanner for wireless ad hoc networks
69、 Multicast topology inference and its applications
70、 Multicast congestion in ring networks
71、 QoS multimedia multicast routing
72、 Overlay networks for peer-to-peer networks
73、 Scheduling data broadcasts on wireless channels : exact solutions and heuristics
74、 Combinatorial and algorithmic issues for microarray analysis
75、 Approximation algorithms for the primer selection, planted motif search, and related problems
76、 Dynamic and fractional programming-based approximation algorithms for sequence alignment with constraints
77、 Approximation algorithms for the selection of robust tag SNPs
78、 Sphere packing and medical applications
79、 Large-scale global placement
80、 Multicommodity flow algorithms for buffered global routing
81、 Algorithmic game theory and scheduling
82、 Approximate economic equilibrium algorithms
83、 Approximation algorithms and algorithm mechanism design
84、 Histograms, wavelets, streams, and approximation
85、 Digital reputation for virtual communities
86、 Color quantization
新书报道