ABSTRACT

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

part |2 pages

Part I: Basic Methodologies

chapter 1|18 pages

Introduction, Overview, and Notation

chapter 2|18 pages

Basic Methodologies and Applications

chapter 3|12 pages

Restriction Methods

chapter 4|14 pages

Greedy Methods

chapter 5|16 pages

Recursive Greedy Methods

chapter 6|12 pages

Linear Programming

chapter 7|12 pages

LP Rounding and Extensions

chapter 9|22 pages

Polynomial-Time Approximation Schemes

chapter 12|12 pages

Randomized Approximation Techniques

chapter 14|18 pages

Empirical Analysis of Randomized Algorithms

chapter 15|16 pages

Reductions That Preserve Approximability

chapter 16|16 pages

Differential Ratio Approximation

chapter 17|16 pages

Hardness of Approximation

part |2 pages

Part II: Local Search, Neural Networks, and Metaheuristics

chapter 18|16 pages

Local Search

chapter 19|14 pages

Stochastic Local Search

chapter 22|14 pages

Neural Networks

chapter 23|12 pages

Principles of Tabu Search

chapter 24|16 pages

Evolutionary Computation

chapter 25|12 pages

Simulated Annealing

chapter 26|14 pages

Ant Colony Optimization

chapter 27|12 pages

Memetic Algorithms

part |2 pages

Part III: Multiobjective Optimization, Sensitivity Analysis, and Stability

part |2 pages

Part IV: Traditional Applications

chapter 34|12 pages

Variable-Sized Bin Packing and Bin Covering

chapter 35|16 pages

Multidimensional Packing Problems

chapter 42|14 pages

Approximations for Steiner Minimum Trees

chapter 45|16 pages

Scheduling Malleable Tasks

chapter 46|10 pages

Vehicle Scheduling Problems in Graphs

chapter 48|18 pages

Generalized Assignment Problem

part |2 pages

Part V: Computational Geometry and Graph Applications

chapter 52|18 pages

Dilation and Detours in Geometric Networks

chapter 54|14 pages

Minimum-Edge Length Rectangular Partitions

chapter 56|16 pages

Maximum Planar Subgraph

chapter 57|16 pages

Edge-Disjoint Paths and Unsplittable Flow

chapter 59|18 pages

Optimum Communication Spanning Trees

chapter 61|20 pages

Hypergraph Partitioning and Clustering

chapter 62|16 pages

Finding Most Vital Edges in a Graph

part |2 pages

Part VI: Large-Scale and Emerging Applications

chapter 70|12 pages

Multicast Congestion in Ring Networks

chapter 71|16 pages

QoS Multimedia Multicast Routing

chapter 72|18 pages

Overlay Networks for Peer-to-Peer Networks

chapter 78|14 pages

Sphere Packing and Medical Applications

chapter 79|20 pages

Large-Scale Global Placement

chapter 81|20 pages

Algorithmic Game Theory and Scheduling

chapter 82|18 pages

Approximate Economic Equilibrium Algorithms

chapter 85|16 pages

Digital Reputation for Virtual Communities

chapter 86|18 pages

Color Quantization