Combinatorial heuristic algorithms with FORTRAN
type: Item
instance of: scholarly article
title: Combinatorial heuristic algorithms with FORTRAN
zbMATH Open document ID: 0629.90055
author: Hang Lau
published in: Lecture Notes in Economics and Mathematical Systems
publication date: 1986-01-01T00:00:00Z
review text: This book provides a source of FORTRAN 77 codes for well-known heuristics in combinatorial optimization. Part 1 is devoted to integer programming problems whereas Part 2 deals with optimization problems in networks. The chapters are independent from each other, start with a short problem description and statement of the algorithm, explain the parameters used in the computer program and contain a test example. Then the listing of the program follows. In particular the following topics are dealt with: An integer linear programming heuristic based on ideas of Hillier, a zero-one linear programming heuristic based on a paper of Toyoda, the approximation algorithm of Ibarra and Kim for zero-one knapsack problems, the Christofides heuristic for travelling salesman problems, a heuristic for the Steiner tree problem based on a paper of Kou, Markowsky and Berman, the two-way graph partitioning procedure and K-median location algorithm of Kerningham and Lin and finally an approximation algorithm for the K-center problem with triangle inequality based on a recent paper of Hochbaum and Shmoys.
reviewed by: Rainer E. Burkard
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90B05
zbMATH DE Number: 4025154
zbMATH Keywords: heuristics
zbMATH Keywords: zero-one knapsack
zbMATH Keywords: travelling salesman
zbMATH Keywords: Steiner tree
zbMATH Keywords: K- median location
zbMATH Keywords: approximation algorithm
zbMATH Keywords: K-center
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 4025154