Handbook of Approximation Algorithms and MetaheuristicsTeofilo F. Gonzalez CRC Press, 2007/05/15 - 1432 ページ 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. |
目次
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 |
| IW-1 | |
Back cover | IW-25 |
他の版 - すべて表示
多く使われている語句
analysis applications approach approximation algorithms approximation ratio assignment bins bound called Chapter combinatorial combinatorial optimization complexity Comput connected consider constant constraints construction contains corresponding cost cover defined denote discussed distributed edges elements example exists feasible Figure function given gives graph heuristic improvement input instance introduced iteration known least Lemma length linear lower bound machine maximization maximum method minimize neighborhood nodes Note objective obtained Oper optimal solution optimization problems optimum packing parameter partition path performance planning points polynomial possible presented probability problem Proc programming proof proved random ratio reduced relaxation respect rounding running satisfies scheduling scheme selected simple solution solve space spanning Steiner step structure studied subset task techniques terminals Theorem tree University variables vector vertex vertices weight