Approximation Algorithms and Metaheuristics
Volume I: Methodologies and Traditional Applications
Editor: Teofilo F. Gonzalez
Second Edition, March 2018
(teo@cs.ucsb.edu)
Table of Contents
Part I: Basic Methodologies
Chapter 1
Introduction, Overview and Notation
Teofilo F. Gonzalez,
University of California, Santa Barbara, CA, USA
Chapter 2
Basic Methodologies and Applications
Teofilo F. Gonzalez,
University of California, Santa Barbara, CA, USA
Chapter 3:
Restriction Methods
Teofilo F. Gonzalez,
University of California, Santa Barbara, CA, USA
Chapter 4:
Greedy Methods
Samir Khuller,
University of Maryland, College Park, MD, USA
Balaji Raghavachari,
University of Texas at Dallas, Richardson, TX, USA
Neal E. Young,
University of California at Riverside, Riverside, CA, USA
Chapter 5:
Recursive Greedy Methods
Guy Even,
Tel-Aviv University, Tel-Aviv, Israel
Chapter 6:
Local Ratio
Dror Rawitz,
Bar Ilan University, Ramat Gan, Israel
Chapter 7:
LP Rounding and Extensions
Daya Ram Gaur,
University of Lethbridge, Lethbridge, Alberta, Canada
Ramesh Krishnamurti,
Simon Fraser University, Burnaby, British Columbia, Canada
Chapter 8:
Polynomial Time Approximation Schemes
Hadas Shachnai,
The Technion, Haifa, Israel
Tami Tamir,
The Interdisciplinary Center, Herzliya, Israel
Chapter 9:
Rounding, Interval Partitioning and Separation
Sartaj Sahni,
University of Florida, Gainesville, FL, USA
Chapter 10:
Asymptotic Polynomial Time Approximation Schemes
Rajeev Motwani,
Stanford University, Stanford, CA, USA
Liadan O'Callaghan,
Google Inc., Mountain View, CA, USA
An Zhu,
Google Inc., Mountain View, CA, USA
Chapter 11:
Randomized Approximation Techniques
Sotiris Nikoletseas,
Patras University, Patras, Greece
Paul Spirakis,
Patras University, Patras, Greece
Chapter 12:
Distributed Approximation Algorithms via LP-duality and Randomization
Devdatt Dubhashi,
Chalmers University, Goteborg, Sweden
Fabrizio Grandoni,
IDSIA, USI-SUPSI, Manno, Switzerland
Alessandro Panconesi,
Università di Roma ``La Sapienza'', Roma, Italy
Chapter 13:
Empirical Analysis of Randomised Algorithms
Holger H. Hoos,
Universiteit Leiden, Leiden, The Netherlands
Thomas Stützle,
Universite Libre de Bruxelles, Brussels, Belgium
Chapter 14:
Reductions that Preserve Approximability
Giorgio Ausiello,
Università degli Studi di Roma ``La Sapienza'', Roma, Italy
Vangelis Th. Paschos,
LAMSADE and Universitá Paris-Dauphine, Paris, France
Chapter 15:
Differential Ratio Approximation
15
Giorgio Ausiello,
Università degli Studi di Roma ``La Sapienza'', Roma, Italy
Vangelis Th. Paschos,
LAMSADE and Universitá Paris-Dauphine, Paris, France
Part II: Local Search, Neural Networks, and Metaheuristics
Chapter 16:
Local Search
16
Roberto Solis-Oba,
The University of Western Ontario, London, Ontario, Canada
Nasim Samei,
The University of Western Ontario, London, Ontario, Canada
Chapter 17:
Stochastic Local Search
Holger H. Hoos,
Universiteit Leiden, Leiden, The Netherlands
Thomas Stützle,
Universitá Libre de Bruxelles, Brussels, Belgium
Chapter 18:
Very Large-Scale Neighborhood Search: Theory, algorithms and Applications
Ravindra K. Ahuja,
Optym, Gainesville, FL, USA
Özlem Ergun,
Northeastern University, Boston, MA, USA
James B Orlin,
Massachusetts Institute of Technology, Cambridge, MA, USA
Abraham P Punnen,
Simon Fraser University, Surrey, British Columbia, Canada
Chapter 19:
Reactive Search: Machine Learning for Memory-Based Heuristics
Roberto Battiti,
University of Trento, Trento, Italy
Mauro Brunato,
University of Trento, Trento, Italy
Chapter 20:
Neural Networks
Bhaskar DasGupta,
University of Illinois at Chicago, Chicago, IL, USA
Derong Liu,
University of Illinois at Chicago, Chicago, IL, USA
Hava T. Siegelmann,
University of Massachusetts, Amherst, MA, USA
Chapter 21:
Principles and Strategies of Tabu Search
Fred Glover,
OptTek Systems, Boulder, CO, USA
Manuel Laguna,
University of Colorado, Boulder, CO, USA
Rafael Martí,
Universidad de Valencia, Valencia, Spain
Chapter 22:
Evolutionary Computation
Guillermo Leguizamón,
Universidad Nacional de San Luis, San Luis, Argentina
Christian Blum,
Universitat Politàcnica de Catalunya, Barcelona, Spain
Enrique Alba,
Universidad de Málaga, Málaga, Spain
Chapter 23:
An Introduction to Ant Colony Optimization
Marco Dorigo,
Universitá Libre de Bruxelles, Brussels, Belgium
Krzysztof Socha,
Universitá Libre de Bruxelles, Brussels, Belgium
Part III:Multiobjective Optimization, Sensitivity Analysis and Stability
Chapter 24:
Stochastic Local Search Algorithms for Multiobjective Combinatorial Optimization: A Review
Luís Paquete,
University of Coimbra, Coimbra, Portugal
Thomas Stützle,
Universitá Libre de Bruxelles, Brussels, Belgium
Chapter 25:
Reoptimization of Hard Optimization Problems
Hans-Joachim Böckenhauer,
ETH Zürich, Zürich, Switzerland
Juraj Hromkoviˇ,
ETH Zürich, Zürich, Switzerland
Dennis Komm,
ETH Zürich, Zürich, Switzerland
Chapter 26:
Sensitivity Analysis in Combinatorial Optimization
David Fernández-Baca,
Iowa State University, Ames, IA, USA
Balaji Venkatachalam,
Iowa State University, Ames, IA, USA
Chapter 27:
Stability of Approximation
Hans-Joachim Böckenhauer,
ETH Zürich, Zürich, Switzerland
Juraj Hromkoviˇ,
ETH Zürich, Zürich, Switzerland
Sebastian Seibert,
RWTH Aachen University, Aachen, Germany
Part IV: Traditional Applications
Chapter 28:
Performance Guarantees for One Dimensional Bin Packing
János Csirik,
University of Szeged, Szeged, Hungary
György Dósa,
University of Pannonia, Veszprám, Hungary
Chapter 29:
Variants of Classical One Dimensional Bin Packing
János Csirik,
University of Szeged, Szeged, Hungary
Csanád Imreh,
University of Szeged, Szeged, Hungary
Chapter 30:
Variable Sized Bin Packing and Bin Covering
János Csirik,
University of Szeged, Szeged, Hungary
Chapter 31:
Multidimensional Packing Problems
Leah Epstein,
University of Haifa, Haifa, Israel
Rob van Stee,
University of Leicester, Leicester, United Kingdom
Chapter 32:
Practical Algorithms for Two-dimensional Packing of Rectangles
Shinji Imahori,
Chuo University, Tokyo, Japan
Mutsunori Yagiura,
Nagoya University, Nagoya, Japan
Hiroshi Nagamochi,
Kyoto University, Kyoto, Japan
Chapter 33:
Practical Algorithms for Two-dimensional Packing of General Shapes
Yannan Hu,
Nagoya University, Nagoya, Japan
Hideki Hashimoto,
Tokyo University of Marine Science and Technology, Tokyo, Japan
Shinji Imahori,
Chuo University, Tokyo, Japan
Mutsunori Yagiura,
Nagoya University, Nagoya, Japan
Chapter 34:
Prize Collecting Traveling Salesman and Related Problems
Giorgio Ausiello,
Università degli Studi di Roma ``La Sapienza'', Roma, Italy
Vincenzo Bonifaci,
Consiglio Nazionale delle Ricerche, Roma, Italy
Stefano Leonardi,
Università degli Studi di Roma ``La Sapienza'', Roma, Italy
Alberto Marchetti-Spaccamela,
Università degli Studi di Roma ``La Sapienza'', Roma, Italy
Chapter 35:
A Development and Deployment Framework for Distributed Branch and Bound
Peter Cappello,
University of California, Santa Barbara, CA, USA
Chris Coakley,
University of California, Santa Barbara, CA, USA
Chapter 36:
Approximations for Steiner Minimum Trees
Ding-Zhu Du,
University of Texas at Dallas, Richardson, TX, USA
Weili Wu,
University of Texas at Dallas, Richardson, TX, USA
Chapter 37:
Practical Approximations of Steiner Trees in Uniform Orientation Metrics
Andrew B. Kahng,
UC San Diego, La Jolla, CA, USA
Ion Mandoiu,
University of Connecticut, Storrs, CT, USA
Alexander Zelikovsky,
Georgia State University, Atlanta, GA, USA
Chapter 38:
Algorithms for Chromatic Sums, Multicoloring, and Scheduling
Dependent Jobs
Magnús M. Halldórsson,
Reykjavik University, Reykjavik, Iceland
Guy Kortsarz,
Rutgers University, Camden, New Jersey
Chapter 39:
Approximation Algorithms and Heuristics for Classical Planning
Jeremy Frank,
NASA Ames Research Center, Moffett Field, CA, USA
Minh Do,
NASA Ames Research Center, Moffett Field, CA, USA
J. Benton,
NASA Ames Research Center, Moffett Field, CA, USA
Chapter 40:
Generalized Assignment Problem
Wei Wu,
Nagoya University, Nagoya, Japan
Mutsunori Yagiura,
Nagoya University, Nagoya, Japan
Toshihide Ibaraki,
The Kyoto College of Graduate Studies for Informatics, Kyoto, Japan
Chapter 41:
Linear Ordering Problem
Celso S. Sakuraba,
Federal University of Sergipe, Sao Cristovao, Brazil
Mutsunori Yagiura,
Nagoya University, Nagoya, Japan
Chapter 42:
Submodular Functions Maximization Problems
Niv Buchbinder,
Tel Aviv University, Tel-Aviv, Israel
Moran Feldman,
The Open University of Israel, Raanana, Israel
