Handbook of approximation algorithms and metaheuristics / edited by Teofilo F. Gonzalez.

Includes bibliographical references and index.

Contents
Part I: Basic Methodologies
1 Introduction, Overview and De.nitions Teo.lo F. Gonzalez ...... 1-1
2 Basic Methodologies and Applications Teo.lo F. Gonzalez ...... 2-1
3 Restriction Methods Teo.lo F. Gonzalez ................. 3-1
4 Greedy Methods Samir Khuller, Balaji Raghavachari, and Neal E. Young
4-1
5 Recursive Greedy Methods Guy Even ................... 5-1
6 Linear Programming Yuval Rabani ..................... 6-1
7 LP Rounding and Extensions Daya Ram Gaur and Ramesh Krishna¡
murti ........................................ 7-1
8 On Analyzing Semide.nite Programming Relaxations of Complex Quadratic Optimization Problems Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang ........................................ 8-1
9 Polynomial Time Approximation Schemes Hadas Shachnai and Tami
Tamir ........................................ 9-1 10 Rounding, Interval Partitioning and Separation Sartaj Sahni ..... 10-1 11 Asymptotic Polynomial Time Approximation Schemes Rajeev Motwani,
Liadan O¿Callaghan, and An Zhu ....................... 11-1 12 Randomized Approximation Techniques Sotiris Nikoletseas and Paul Spi¡rakis ........................................ 12-1
13 Distributed Approximation Algorithms via LP-duality and Randomiza¡tion Devdatt Dubhashi, Fabrizio Grandoni, and Alessandro Panconesi 13-1 14 Empirical Analysis of Randomised Algorithms Holger H. Hoos and Thomas St¿
utzle ....................................... 14-1 15 Reductions that Preserve Approximability Giorgio Ausiello and Vangelis Th. Paschos .................................... 15-1 16 Di.erential Ratio Approximation Giorgio Ausiello and Vangelis Th. Paschos
16-1
17 Hardness of Approximation Mario Szegedy ................ 17-1
Part II: Local Search, Neural Networks, and Meta-heuristics
18 Local Search Roberto Solis-Oba ....................... 18-1 19 Stochastic Local Search Holger H. Hoos and Thomas St¿
utzle ..... 19-1 ¿
20 Very Large Neighborhood Search Ravindra K. Ahuja, Olem Ergun, James B Orlin, and Abraham P Punnen ....................... 20-1 21 Reactive Search: Machine Learning for Memory-Based Heuristics Roberto Battiti and Mauro Brunato .......................... 21-1 22 Neural Networks Bhaskar DasGupta, Derong Liu, and Hava T. Siegel-mann ........................................ 22-1
23 Principles of Tabu Search Fred Glover, Manuel Laguna, and Rafael Mart´i
23-1
24 Evolutionary Computation Guillermo Leguizam´
on, Christian Blum, and
Enrique Alba ................................... 24-1
25 Simulated Annealing Emile Aarts, Jan Korst, and Wil Michiels ... 25-1
26 An Introduction to Ant Colony Optimization Marco Dorigo and Krzysztof
Socha ........................................ 26-1
27 Memetic Algorithms Carlos Cotta and Pablo Moscato ......... 27-1
Part III: Multiobjective Optimization, Sensitivity Analysis and Stability
28 Approximation in Multiobjective Problems Eric Angel, Evripidis Bampis,
and Laurent Gourv`es .............................. 28-1
29 Stochastic Local Search Algorithms for Multiobjective Combinatorial Op-
29-1
timization: A Review Lu´is Paquete and Thomas St¿
utzle ........
30 Sensitivity Analysis in Combinatorial Optimization David Fern´
andez-
Baca and Balaji Venkatachalam ........................ 30-1
31 Stability of Approximation Hans-Joachim B¿
ockenhauer, Juraj Hromkovic,
and Sebastian Seibert .............................. 31-1
Part IV: Traditional Applications
32 Performance Guarantees for One Dimensional Bin Packing Edward G.
32-1
Co.man, Jr. and J´
anos Csirik .........................
33 Variants of Classical One Dimensional Bin Packing Edward G. Co.man,
Jr.,
J´
anos Csirik, and Joseph Y-T. Leung .................. 33-1
34 Variable Sized Bin Packing and Bin Covering Edward G. Co.man, Jr.,
J´
anos Csirik, and Joseph Y-T. Leung .................... 34-1
35 Multidimensional Packing Problems Rob van Stee and Leah Epstein 36 Practical Algorithms for Two-dimensional Packing Shinji Imahori, Mut-
35-1
sunori Yagiura, and Hiroshi Nagamochi ................... 36-1
37 A Generic Primal-Dual Approximation Algorithm for an Interval Packing
and Stabbing Problem So.a Kovaleva and Frits C.R. Spieksma ... 37-1
38 Approximation Algorithms for Facility Dispersion S. S. Ravi, Daniel J.
Rosenkrantz, and Giri K. Tayi ......................... 38-1
39 Greedy Algorithms for Metric Facility Location Problems Anthony Man-
Cho So, Yinyu Ye, and Jiawei Zhang ..................... 39-1
40 Prize Collecting Traveling Salesman and Related Problems Giorgio Ausiello,
Vincenzo Bonifaci, Stefano Leonardi, and Alberto Marchetti-Spaccamela 40-1
41 A Development and Deployment Framework for Distributed Branch and
Bound Peter Cappello and Chris Coakley ................. 41-1
42 Approximations for Steiner Minimum Trees Ding-Zhu Du and Weili Wu 42-1
43 Practical Approximations of Steiner Trees in Uniform Orientation Metrics
Andrew B. Kahng, Ion Mandoiu, and Alexander Zelikovsky ....... 43-1
44 Approximation Algorithms for Imprecise Computation Tasks with 0/1
Constraint Joseph Y-T. Leung ....................... 44-1
45 Scheduling Malleable Tasks Klaus Jansen and Hu Zhang ....... 45-1
46 Vehicle Scheduling Problems in Graphs Yoshiyuki Karuno and Hiroshi
Nagamochi ..................................... 46-1
47 Approximation Algorithms and Heuristics for Classical Planning Jeremy
48 Generalized Assignment Problem Mutsunori Yagiura and Toshihide Ibaraki
Frank and Ari Jonsson ............................. 47-1
48-1
49 Probabilistic Greedy Heuristics for Satis.ability Problems Rajeev Kohli
and Ramesh Krishnamurti ........................... 49-1
Stanley P. Y. Fung, Cao-An Wang, and Francis Y. L. Chin ....... 50-1
51 Approximation Schemes for Minimum-Cost k-Connectivity Problems in
Geometric Graphs Artur Czumaj and Andrzej Lingas ......... 51-1
52 Dilation and Detours in Geometric Networks Joachim Gudmundsson
53 The Well-Separated Pair Decomposition and Its Applications Michiel
54 Minimum Edge Length Rectangular Partitions Teo.lo F. Gonzalez and
55 Partitioning Finite d-Dimensional Integer Grids with Applications Silvia
58 Approximating Minimum Cost Connectivity Problems Guy Kortsarz and
59 Optimum Communication Spanning Trees Bang Ye Wu, Chuan Yi Tang,
60 Approximation Algorithms for Multilevel Graph Partitioning Burkhard
61 Hypergraph Partitioning and Clustering David A. Papa and Igor L.
63 Stochastic Local Search Algorithms for the Graph Colouring Problem
and Christian Knauer .............................. 52-1
Smid ........................................ 53-1
Si Qing Zheng ................................... 54-1
Part V: Computational Geometry and Graph Ap¡plications
50 Approximation Algorithms for Some Optimal 2D and 3D Triangulations
Ghilezan, Jovanka Pantovi´c, and Jovisa Zuni´c ............... 55-1
56 Maximum Planar Subgraph Gruia Calinescu and Cristina G. Fernandes 56-1
57 Edge-Disjoint Paths and Unsplittable Flow Stavros G. Kolliopoulos . 57-1
Zeev Nutov .................................... 58-1
and Kun-Mao Chao ............................... 59-1
Monien, Robert Preis, and Stefan Schamberger .............. 60-1
Markov ....................................... 61-1
62 Finding Most Vital Edges in a Graph Hong Shen ............ 62-1
Marco Chiarandini, Irina Dumitrescu, and Thomas St¿
utzle ....... 63-1
64 On Solving the Maximum Disjoint Paths Problem with Ant Colony Op
¡timization Maria J. Blesa and Christian Blum .............. 64-1
Part VI: Large-Scale and Emerging Applications
65 Cost-E.cient Multicast Routing in Ad Hoc and Sensor Networks Pedro
M.
Ruiz and Ivan Stojmenovic ......................... 65-1
66 Approximation Algorithm for Clustering in Ad-hoc Networks Lan Wang
67 Topology Control Problems for Wireless Ad hoc Networks Errol L. Lloyd
and Stephan Olariu ............................... 66-1
and S. S. Ravi ................................... 67-1
Yu Wang ...................................... 68-1
69 Multicast Topology Inference and Its Applications Hui Tian and Hong
Shen ........................................ 69-1
70 Multicast Congestion in Ring Networks SingLing Lee, RongJou Yang,
and Hann-Jang Ho ................................ 70-1
71 QoS Multimedia Multicast Routing Ion Mandoiu, Alex Olshevsky, and
Alexander Zelikovsky .............................. 71-1
72 Overlay Networks for Peer-to-Peer Networks Andr´ea W. Richa and Chris
¡
tian Scheideler .................................. 72-1
73 Scheduling Data Broadcasts on Wireless Channels: Exact Solutions and
Heuristics Alan A. Bertossi, M. Cristina Pinotti, and Romeo Rizzi . 73-1
74 Combinatorial and Algorithmic Issues for Microarray Analysis Carlos
Cotta, Michael A. Langston, and Pablo Moscato ............. 74-1
75 Approximation Algorithms for the Primer Selection, Planted Motif Search,
and Related Problems Sudha Balla, Jaime Davila, and Sanguthevar Ra¡
jasekaran ...................................... 75-1
76 Dynamic and Fractional Programming based Approximation Algorithms
Egecioglu ..................................... 76-1
77 Approximation Algorithms for the Selection of Robust Tag SNPs Yao-
Ting Huang, Kui Zhang, Ting Chen, and Kun-Mao Chao ........ 77-1
78 Sphere Packing and Medical Applications Danny Z. Chen and Jinhui
Xu .......................................... 78-1
79 Large-Scale Global Placement Jason Cong and Joseph R. Shinnerl . 79-1
80 Multicommodity Flow Algorithms for Bu.ered Global Routing Christoph
Albrecht, Andrew B. Kahng, Ion Mandoiu, and Alexander Zelikovsky 80-1
81 Algorithmic Game Theory and Scheduling Eric Angel, Evripidis Bampis,
and Fanny Pascual ................................ 81-1
82 Approximate Economic Equilibrium Algorithms Xiaotie Deng and Li-
Sha Huang ..................................... 82-1
83 Approximation Algorithms and Algorithm Mechanism Design Xiang-
Yang Li and Weizhao Wang .......................... 83-1
84 Histograms, Wavelets, Streams and Approximation Sudipto Guha .. 84-1
85 Digital Reputation for Virtual Communities Roberto Battiti and Anurag
68 Geometrical Spanner for Wireless Ad Hoc Networks Xiang-Yang Li and
¿
for Sequence Alignment with Constraints Abdullah N. Arslan and Omer
Garg ........................................ 85-1
86 Color Quantization Zhigang Xiang ..................... 86-1
I
Basic Methodologies
10 Rounding, Interval Partitioning and Separation Sartaj Sahni . . . . . 10-1 11 Asymptotic Polynomial Time Approximation Schemes Rajeev Motwani, Liadan O¿Callaghan, and An Zhu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-1 12 Randomized Approximation Techniques Sotiris Nikoletseas and Paul Spirakis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-1
13 Distributed Approximation Algorithms via LP-duality and Randomization Devdatt Dubhashi, Fabrizio Grandoni, and Alessandro Panconesi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-1
14 Empirical Analysis of Randomised Algorithms Holger H. Hoos and Thomas St¿
utzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14-1 15 Reductions that Preserve Approximability Giorgio Ausiello and Vangelis Th. Paschos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15-1 16 Di.erential Ratio Approximation Giorgio Ausiello and Vangelis Th. Paschos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16-1 17 Hardness of Approximation Mario Szegedy . . . . . . . . . . . . . . . . . . . . . . . . . . 17-1
I-1

Using both practical and theoretical points of view, Handbook of Approximation Algorithms and Metaheuristics provides complete coverage of design and approximation methodologies. Tutorial in nature, the book emphasizes techniques that help readers design approximation algorithms using metaheuristic approaches such as simulated annealing, genetic algorithms, ant colony, evolutionary computation, tabu search, and neural networks. Offering a historical perspective, it presents various applications that illustrate many of the techniques included in the text. It also addresses application fields such as bin packaging, traveling sales person problem, Steiner Trees, clustering, and more.