Handbook of Approximation Algorithms and Metaheuristics

Front Cover
Teofilo F. Gonzalez
CRC Press, May 15, 2007 - Computers - 1432 pages
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Chapter 2 Basic Methodologies and Applications
2-1
Chapter 3 Restriction Methods
3-1
Chapter 4 Greedy Methods
4-1
Chapter 5 Recursive Greedy Methods
5-1
Chapter 6 Linear Programming
6-1
Chapter 7 LP Rounding and Extensions
7-1
Chapter 8 On Analyzing Semidefinite Programmng Relaxations of Complex Quadratic Optimization Problems
8-1
Chapter 9 PolynomialTime Approximation Schemes
9-1
Chapter 46 Vehicle Scheduling Problems in Graphs
46-1
Chapter 47 Approximation Algorithms and Heuristics for Classical Planning
47-1
Chapter 48 Generalized Assignment Problem
48-1
Chapter 49 Probabilistic Greedy Heuristics for Satisfiability Problems
49-1
Computational Geometry and Graph Applications
49-11
Chapter 50 Approximation Algorithms for Some Optimal 2D and 3D Triangulations
50-1
Chapter 51 Approximation Schemes for MinimumCost kConnectivity Problems in Geometric Graphs
51-1
Chapter 52 Dilation and Detours in Geometric Networks
52-1

Chapter 10 Rounding Interval Partitioning and Separation
10-1
Chapter 11 Asymptotic PolynomialTime Approximation Schemes
11-1
Chapter 12 Randomized Approximation Techniques
12-1
Chapter 13 Distributed Apporximation Algorithms via LPDuality and Randomization
13-1
Chapter 14 Empirical Analysis of Randomized Algorithms
14-1
Chapter 15 Reductions That Preserve Approximability
15-1
Chapter 16 Differential Ratio Approximation
16-1
Chapter 17 Hardness of Approximation
17-1
Local Search Neural Networks and Metaheuristics
17-17
Chapter 18 Local Search
18-1
Chapter 19 Stochastic Local Search
19-1
Theory Algorithms and Applications
20-1
Machine Learning for MemoryBased Heuristics
21-1
Chapter 22 Neural Networks
22-1
Chapter 23 Principles of Tabu Search
23-1
Chapter 24 Evolutionary Computation
24-1
Chapter 25 Simulated Annealing
25-1
Chapter 26 Ant Colony Optimization
26-1
Chapter 27 Memetic Algorithms
27-1
Multiobjective Optimization Sensitivity Analysis and Stability
27-13
Chapter 28 Approximation in Multiobjective Problems
28-1
A Review
29-1
Chapter 30 Sensitivity Analysis in Combinatorial Optimization
30-1
Chapter 31 Stability of Approximation
31-1
Traditional Applications
31-15
Chapter 32 Performance Guarantees for OneDimensional Bin Packing
32-1
Chapter 33 Variants of Classical OneDimensional Bin Packing
33-1
Chapter 34 VariableSized Bin Packing and Bin Covering
34-1
Chapter 35 Multidimensional Packing Problems
35-1
Chapter 36 Practical Algorithms for TwoDimensional Packing
36-1
Chapter 37 A Generic PrimalDual Approximation Algorithm for an Interval Packing and Sstabbing Problem
37-1
Chapter 38 Approximation Algorithms for Facility Dispersion
38-1
Chapter 39 Greedy Algorithms for Metric Facility Location Problems
39-1
Chapter 40 PrizeCollecting Traveling Salesman and Related Problems
40-1
Chapter 41 A Development and Deployment Framework for Distributed Branch and Bound
41-1
Chapter 42 Approximations for Steiner Minimum Trees
42-1
Chapter 43 Practical Approximations of Steiner Trees in Uniform Orientation Metrics
43-1
Chapter 44 Approximation Algorithms for Imprecise Computation Task with 01 Constraint
44-1
Chapter 45 Scheduling Malleable Tasks
45-1
Chapter 53 The WellSeparated Pair Decomposition and Its Applications
53-1
Chapter 54 MinimumEdge Length Rectangular Partitions
54-1
Chapter 55 Partitioning Finite dDimensional Integer Grids with Applications
55-1
Chapter 56 Maximum Planar Subgraph
56-1
Chapter 57 EdgeDisjoint Paths and Unsplittable Flow
57-1
Chapter 58 Approximating MinimumCost Connectivity Problems
58-1
Chapter 59 Optimum Communication Spanning Trees
59-1
Chapter 60 Approximation Algorithms for Multilevel Graph Partitioning
60-1
Chapter 61 Hypergraph Partitioning and Clustering
61-1
Chapter 62 Finding Most Vital Edges in a Graph
62-1
Chapter 63 Stochastic Local Search Algorithms for the Graph Coloring Problem
63-1
Chapter 64 On Solving the Maximum Disjoint Paths Problem with Ant Colony Optimization
64-1
LargeScale and Emerging Applications
64-17
Chapter 65 CostEfficient Multicast Routing in Ad Hoc and Sensor Networks
65-1
Chapter 66 Approximation Algorithm for Clustering in Ad Hoc Networks
66-1
Chapter 67 Topology Control Problems for Wireless Ad Hoc Networks
67-1
Chapter 68 Geometrical Spanner for Wireless Ad Hoc Networks
68-1
Chapter 69 Multicast Topology Inference and Its Applications
69-1
Chapter 70 Multicast Congestion in Ring Networks
70-1
Chapter 71 QoS Multimedia Multicast Routing
71-1
Chapter 72 Overlay Networks for PeertoPeer Networks
72-1
Exact Solutions and Heuristics
73-1
Chapter 74 Combinatorial and Algorithmic Issues for Microarray Analysis
74-1
Chapter 75 Approximation Algorithms for the Primer Selection Planted Motif Search and Related Problems
75-1
Chapter 76 Dynamic and Fractional ProgrammingBased Approximation Algorithms for Sequence Alignment with Constraints
76-1
Chapter 77 Approximation Algorithms for the Selection of Robust Tag SNPs
77-1
Chapter 78 Sphere Packing and Medical Applications
78-1
Chapter 79 LargeScale Global Placement
79-1
Chapter 80 Multicommodity Flow Algorithms for Buffered Global Routing
80-1
Chapter 81 Algorithmic Game Theory and Scheduling
81-1
Chapter 82 Approximate Economic Equilibrium Algorithms
82-1
Chapter 83 Approximation Algorithms and Algorithm Mechanism Design
83-1
Chapter 84 Histograms Wavelets Streams and Approximation
84-1
Chapter 85 Digital Reputation for Virtual Communities
85-1
Chapter 86 Color Quantization
86-1
Index
IW-1
Back cover
IW-25
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information