Skip to Content

Handbook of Approximation Algorithms and Metaheuristics

Edited by Teofilo F. Gonzalez

Series Editor: Sartaj Sahni

Contributors: Rajeev Motwani, Samir Khuller, Balaji Raghavachari, James Orlin, Ravindra K. Ahuja, Andrew B. Kahng, Ivan Stojmenovic, Ting Chen, Joseph Y-T. Leung, Hong Shen, Kun-Mao Chao, Bang Ye Wu, Xiang-Yang Li, Artur Czumaj, Michiel Smid, Wei li Wu, Stephan Olariu, Derong Liu, G. Arslan, Gruia Calinescu, Kui Zhang, Fred Glover, Enrique Alba, Carlos Cotta, Sotiris Nikoletseas, Paul G. Spirakis, Sanguthevar Rajasekaran, Bhaskar Dasgupta, Hava Siegelmann, Guillermo Leguizamon, Rafael Marti, Jeremy Frank, David Fernandez-Baca, Balaji Venkatachalam, Hu Zhang, Hiroshi Nagamochi, Mutsunori Yagiura, Shinji Imahori, Cristina Gomes Fernandes, Weizhao Wang, Toshihide Ibaraki, Stavros Kolliopoulos, Zhigang Xiang, Yoshiyuki Karuno, Ari Jonsson, Leah Epstein, Danny Chen, Jinhui Xu, Guy Even, Christian Knauer, Roberto Solis-Oba, Si Qing Zheug, Igor L. Markov, Liadan O'Callaghan, An Zhu, Stanley P.Y. Fung, Christopher Coakley, Peter Cappello, Yin Yu Ye, Jiawei Zhang, Roberto Battiti, Ion Mandoiu, Alexander Zelikovsky, Joachim Gudmundsson, Burkhard Monien, Robert Preis, Stefan Schamberger, Vangelis Th. Paschos, Alan Bertossi, Cristina Pinotti, Romeo Rizzi, Pablo Moscato, Ramesh Krishnamurti, Giorgio Ausiello, Jason Cong, Joseph R. Shinnerl, Jan Korst, Wil Michiels, Emile Aarts, Jovisa Junic, Jovanka Pantovic, Silvia Ghilezan, Alessandro Panconesi, Fabrizio Grandoni, Krzysztof Socha, Marco Dorigo, David Papa, Marco Chiarandini, Francis Yuk-Lun Chin, Hann-Jang HO, Klaus Jansen, Michael A. Langston, Rob Van Stee, Chuan Yi Tang, Yu WANG, Rongjou Yang, Neal E. Young, Sudha Balla, Jaime Davila, Ding-Zhu DU, Sudipto Guha, Hans-Joachim Bockenhauer, Xiaotie Deng, Juraj Hromkovic, Jovisa Zunic, Luis Filipe Paquete, Sebastian Seibert, Anurag Garg, Christian Blum, Li-Sha Huang, Cao An Wang, Mario Szegedy, Omer Egecioglu, Manuel Laguna, Mauro Brunato, Thomas Stutzle, Yao-Ting Huang, Christian Scheideler, Irina Dumitrescu, Holger Hoos, Andrzey Lingas, Giri K. Tayi, S.S. Ravi, Zeev Nutov, Tami Tamir, Hadas Shachnai, Maria J Blesa, Daya Ram Gaur, Singling Lee, Anthony Man-Cho SO, Christoph Albrecht, Ozlem Ergun, Daniel J. Rosenkrantz, Andrea Werneck Richa, Pedro M. Ruiz, Edward G. Coffman, Jr., Alexander Olshevsky, Errol Lynn Lloyd, Frits C.R. Spieksma, Sofia Kovaleva, Janos Csirik, Vincenzo Bonifaci, Stefano Leonardi, Alberto Marchetti-Spaccamela, Fanny Pascual, Eric Angel, Evripidis Bampis, Guy Kortsarz, Laurent Gourves, Yuval Rabani, Devdatt Dubhashi, Abraham P. Punnen, Hui Tian, Rajeev Kohli, Lan Wang

Published May 15th 2007 by Chapman and Hall/CRC – 1,432 pages

Series: Chapman & Hall/CRC Computer & Information Science Series

Purchasing Options:

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.

Reviews

"Therefore the existence of a reference such as this Handbook of Approximation Algorithms and Metaheuristics is very welcome and useful . . . Experts can find inspiration for further work, while those not familiar with this issue can, in a very elegant way, start to learn it."

– Kristina Šoric, in Zentralblatt Math, 2008

Contents

PREFACE

BASIC METHODOLOGIES

Introduction, Overview, and Notation

Basic Methodologies and Applications

Restriction Methods

Greedy Methods

Recursive Greedy Methods

Linear Programming

LP Rounding and Extensions

On Analyzing Semidefinite Programming Relaxations of Complex

Quadratic Optimization Problems

Polynomial-Time Approximation Schemes

Rounding, Interval Partitioning, and Separation

Asymptotic Polynomial-Time Approximation Schemes

Randomized Approximation Techniques

Distributed Approximation Algorithms via LP-Duality and Randomization

Empirical Analysis of Randomized Algorithms

Reductions that Preserve Approximability

Differential Ratio Approximation

Hardness of Approximation

LOCAL SEARCH, NEURAL NETWORKS, AND METAHEURISTICS

Local Search

Stochastic Local Search

Very Large-Scale Neighborhood Search: Theory, Algorithms, and Applications

Reactive Search: Machine Learning for Memory-Based Heuristics

Neural Networks

Principles of Tabu Search

Evolutionary Computation

Simulated Annealing

Ant Colony Optimization

Memetic Algorithms

MULTIOBJECTIVE OPTIMIZATION, SENSITIVITY ANALYSIS, AND STABILITY

Approximation in Multiobjective Problems

Stochastic Local Search Algorithms for Multiobjective Combinatorial Optimization: A Review

Sensitivity Analysis in Combinatorial Optimization

Stability of Approximation

TRADITIONAL APPLICATIONS

Performance Guarantees for One-Dimensional Bin Packing

Variants of Classical One-Dimensional Bin Packing

Variable, Sized Bin Packing and Bin Covering

Multidimensional Packing Problems

Practical Algorithms for Two-Dimensional Packing

A Generic Primal-Dual Approximation Algorithm for an Interval Packing and Stabbing Problem

Approximation Algorithms for Facility Dispersion

Greedy Algorithms for Metric Facility Location Problems

Prize-Collecting Traveling Salesman and Related Problems

A Development and Deployment Framework for Distributed Branch and Bound

Approximations for Steiner Minimum Trees

Practical Approximations of Steiner Trees in Uniform Orientation Metrics

Approximation Algorithms for Imprecise Computation Tasks with 0/1 Constraint

Scheduling Malleable Tasks

Vehicle Scheduling Problems in Graphs

Approximation Algorithms and Heuristics for Classical Planning

Generalized Assignment Problem

Probabilistic Greedy Heuristics for Satisfiability Problems

COMPUTATIONAL GEOMETRY AND GRAPH APPLICATIONS

Approximation Algorithms for Some Optimal 2D and 3D Triangulations

Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs

Dilation and Detours in Geometric Networks

The Well-Separated Pair Decomposition and its Applications

Minimum-Edge Length Rectangular Partitions

Partitioning Finite d-Dimensional Integer Grids with Applications

Maximum Planar Subgraph

Edge-Disjoint Paths and Unsplittable Flow

Approximating Minimum-Cost Connectivity Problems

Optimum Communication Spanning Trees

Approximation Algorithms for Multilevel Graph Partitioning

Hypergraph Partitioning and Clustering

Finding Most Vital Edges in a Graph

Stochastic Local Search Algorithms for the Graph Coloring Problem

On Solving the Maximum Disjoint Paths Problem with Ant Colony Optimization

LARGE-SCALE AND EMERGING APPLICATIONS

Cost-Efficient Multicast Routing in Ad Hoc and Sensor Networks

Approximation Algorithm for Clustering in Ad Hoc Networks

Topology Control Problems for Wireless Ad Hoc Networks

Geometrical Spanner for Wireless Ad Hoc Networks

Multicast Topology Inference and its Applications

Multicast Congestion in Ring Networks

QoS Multimedia Multicast Routing

Overlay Networks for Peer-to-Peer Networks

Scheduling Data Broadcasts on Wireless Channels: Exact Solutions and Heuristics

Combinatorial and Algorithmic Issues for Microarray Analysis

Approximation Algorithms for the Primer Selection, Planted Motif Search, and Related Problems

Dynamic and Fractional Programming-Based Approximation Algorithms for Sequence Alignment with Constraints

Approximation Algorithms for the Selection of Robust Tag SNPs

Sphere Packing and Medical Applications

Large-Scale Global Placement

Multicommodity Flow Algorithms for Buffered Global Routing

Algorithmic Game Theory and Scheduling

Approximate Economic Equilibrium Algorithms

Approximation Algorithms and Algorithm Mechanism Design

Histograms, Wavelets, Streams, and Approximation

Digital Reputation for Virtual Communities

Color Quantization

INDEX

Name: Handbook of Approximation Algorithms and Metaheuristics (Hardback) – Chapman and Hall/CRC 
Description: Edited by Teofilo F. GonzalezSeries Editor: Sartaj SahniContributors: Rajeev Motwani, Samir Khuller, Balaji Raghavachari, James Orlin, Ravindra K. Ahuja, Andrew B. Kahng, Ivan Stojmenovic, Ting Chen, Joseph Y-T. Leung, Hong Shen, Kun-Mao Chao, Bang Ye Wu, Xiang-Yang Li, Artur Czumaj, Michiel Smid, Wei li Wu, Stephan Olariu, Derong Liu, G. Arslan, Gruia Calinescu, Kui Zhang, Fred Glover, Enrique Alba, Carlos Cotta, Sotiris Nikoletseas, Paul G. Spirakis, Sanguthevar Rajasekaran, Bhaskar Dasgupta, Hava Siegelmann, Guillermo Leguizamon, Rafael Marti, Jeremy Frank, David Fernandez-Baca, Balaji Venkatachalam, Hu Zhang, Hiroshi Nagamochi, Mutsunori Yagiura, Shinji Imahori, Cristina Gomes Fernandes, Weizhao Wang, Toshihide Ibaraki, Stavros Kolliopoulos, Zhigang Xiang, Yoshiyuki Karuno, Ari Jonsson, Leah Epstein, Danny Chen, Jinhui Xu, Guy Even, Christian Knauer, Roberto Solis-Oba, Si Qing Zheug, Igor L. Markov, Liadan O'Callaghan, An Zhu, Stanley P.Y. Fung, Christopher Coakley, Peter Cappello, Yin Yu Ye, Jiawei Zhang, Roberto Battiti, Ion Mandoiu, Alexander Zelikovsky, Joachim Gudmundsson, Burkhard Monien, Robert Preis, Stefan Schamberger, Vangelis Th. Paschos, Alan Bertossi, Cristina Pinotti, Romeo Rizzi, Pablo Moscato, Ramesh Krishnamurti, Giorgio Ausiello, Jason Cong, Joseph R. Shinnerl, Jan Korst, Wil Michiels, Emile Aarts, Jovisa Junic, Jovanka Pantovic, Silvia Ghilezan, Alessandro Panconesi, Fabrizio Grandoni, Krzysztof Socha, Marco Dorigo, David Papa, Marco Chiarandini, Francis Yuk-Lun Chin, Hann-Jang HO, Klaus Jansen, Michael A. Langston, Rob Van Stee, Chuan Yi Tang, Yu WANG, Rongjou Yang, Neal E. Young, Sudha Balla, Jaime Davila, Ding-Zhu DU, Sudipto Guha, Hans-Joachim Bockenhauer, Xiaotie Deng, Juraj Hromkovic, Jovisa Zunic, Luis Filipe Paquete, Sebastian Seibert, Anurag Garg, Christian Blum, Li-Sha Huang, Cao An Wang, Mario Szegedy, Omer Egecioglu, Manuel Laguna, Mauro Brunato, Thomas Stutzle, Yao-Ting Huang, Christian Scheideler, Irina Dumitrescu, Holger Hoos, Andrzey Lingas, Giri K. Tayi, S.S. Ravi, Zeev Nutov, Tami Tamir, Hadas Shachnai, Maria J Blesa, Daya Ram Gaur, Singling Lee, Anthony Man-Cho SO, Christoph Albrecht, Ozlem Ergun, Daniel J. Rosenkrantz, Andrea Werneck Richa, Pedro M. Ruiz, Edward G. Coffman, Jr., Alexander Olshevsky, Errol Lynn Lloyd, Frits C.R. Spieksma, Sofia Kovaleva, Janos Csirik, Vincenzo Bonifaci, Stefano Leonardi, Alberto Marchetti-Spaccamela, Fanny Pascual, Eric Angel, Evripidis Bampis, Guy Kortsarz, Laurent Gourves, Yuval Rabani, Devdatt Dubhashi, Abraham P. Punnen, Hui Tian, Rajeev Kohli, Lan Wang. 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...
Categories: Discrete Mathematics, Algorithms & Complexity, Computer Engineering