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

    AAM Volume II, Table of Contents

    AAM First Edition, Table of Contents

    AAM First Edition List of Contibutors (Alphabetic wrt first name)