Hardcover ISBN:  9780821808344 
Product Code:  DIMACS/40 
List Price:  $114.00 
MAA Member Price:  $102.60 
AMS Member Price:  $91.20 
eBook ISBN:  9781470439989 
Product Code:  DIMACS/40.E 
List Price:  $107.00 
MAA Member Price:  $96.30 
AMS Member Price:  $85.60 
Hardcover ISBN:  9780821808344 
eBook: ISBN:  9781470439989 
Product Code:  DIMACS/40.B 
List Price:  $221.00 $167.50 
MAA Member Price:  $198.90 $150.75 
AMS Member Price:  $176.80 $134.00 
Hardcover ISBN:  9780821808344 
Product Code:  DIMACS/40 
List Price:  $114.00 
MAA Member Price:  $102.60 
AMS Member Price:  $91.20 
eBook ISBN:  9781470439989 
Product Code:  DIMACS/40.E 
List Price:  $107.00 
MAA Member Price:  $96.30 
AMS Member Price:  $85.60 
Hardcover ISBN:  9780821808344 
eBook ISBN:  9781470439989 
Product Code:  DIMACS/40.B 
List Price:  $221.00 $167.50 
MAA Member Price:  $198.90 $150.75 
AMS Member Price:  $176.80 $134.00 

Book DetailsDIMACS  Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 40; 1998; 461 ppMSC: Primary 03; 90; 68
Connectivity and facilities location are two important topics in network design, with applications in data communication, transportation, production planning, and VLSI designs. There are two issues concerning these topics: design and optimization. They involve combinatorial design and combinatorial optimization. This volume features talks presented at an interdisciplinary research workshop held at DIMACS in April 1997. The workshop was attended by leading theorists, algorithmists, and practitioners working on network design problems.
Finding the solution of design problems and the optimal or approximate solution of the related optimization problem are challenging tasks because no polynomial time algorithms are known. Such problems include some variations of Steiner tree problems (such as multipleconnected Steiner network, independent flow problem, and subsetinterconnection designs), topology network design, nonlinear assignment problems (such as quadratic assignment problems), problems in facilities location and allocation, and network problems appearing in VLSI design.
The focus of this book is on combinatorial, algorithmic, and applicational aspects of these problems. The volume would be suitable as a textbook for advanced courses in computer science, mathematics, engineering, and operations research.
Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were copublished with the Association for Computer Machinery (ACM).
ReadershipGraduate students, research mathematicians, computer scientists and operations researchers working on network design problems.

Table of Contents

Chapters

Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

Differential greedy for the 0–1 equicut problem

Gradientconstrained minimal Steiner trees

The Steiner tree problem for terminals on the boundary of a rectilinear polygon

Using Hadwiger numbers in network design

Reducing the graphical Steiner problem with a sensitivity test

A frequency assignment problem in cellular phone networks

An optimal greedy algorithm for wavelength allocation in directed tree networks

A GRASP algorithm for the single source uncapacitated minimum concavecost network flow problem

Approximation results for the optimum cost chromatic partition problem

Approximating dense cases of covering problems

Connected facility location problems

Constrained spanning tree problems: Approximate methods and parallel computation

Star, grid, ring topologies in facility location & network design

Network improvement problems

Improved results on serviceconstrained network design problems

A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem

A generalized threshold algorithm for the shortest path problem with time windows

A case study of derandomization methods for combinatorial approximation algorithms

A chunking based genetic algorithm for the Steiner tree problem in graphs

A new exact algorithm for rectilinear Steiner trees

A scalable TWDM lightwave network based on generalized de Bruijn digraph

A new model of generalized Steiner trees and 3coordinate systems

A model for network design

Nonlinear and mixedinteger optimization in chemical process network systems

Shortest networks on spheres


RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Requests
Connectivity and facilities location are two important topics in network design, with applications in data communication, transportation, production planning, and VLSI designs. There are two issues concerning these topics: design and optimization. They involve combinatorial design and combinatorial optimization. This volume features talks presented at an interdisciplinary research workshop held at DIMACS in April 1997. The workshop was attended by leading theorists, algorithmists, and practitioners working on network design problems.
Finding the solution of design problems and the optimal or approximate solution of the related optimization problem are challenging tasks because no polynomial time algorithms are known. Such problems include some variations of Steiner tree problems (such as multipleconnected Steiner network, independent flow problem, and subsetinterconnection designs), topology network design, nonlinear assignment problems (such as quadratic assignment problems), problems in facilities location and allocation, and network problems appearing in VLSI design.
The focus of this book is on combinatorial, algorithmic, and applicational aspects of these problems. The volume would be suitable as a textbook for advanced courses in computer science, mathematics, engineering, and operations research.
Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were copublished with the Association for Computer Machinery (ACM).
Graduate students, research mathematicians, computer scientists and operations researchers working on network design problems.

Chapters

Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

Differential greedy for the 0–1 equicut problem

Gradientconstrained minimal Steiner trees

The Steiner tree problem for terminals on the boundary of a rectilinear polygon

Using Hadwiger numbers in network design

Reducing the graphical Steiner problem with a sensitivity test

A frequency assignment problem in cellular phone networks

An optimal greedy algorithm for wavelength allocation in directed tree networks

A GRASP algorithm for the single source uncapacitated minimum concavecost network flow problem

Approximation results for the optimum cost chromatic partition problem

Approximating dense cases of covering problems

Connected facility location problems

Constrained spanning tree problems: Approximate methods and parallel computation

Star, grid, ring topologies in facility location & network design

Network improvement problems

Improved results on serviceconstrained network design problems

A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem

A generalized threshold algorithm for the shortest path problem with time windows

A case study of derandomization methods for combinatorial approximation algorithms

A chunking based genetic algorithm for the Steiner tree problem in graphs

A new exact algorithm for rectilinear Steiner trees

A scalable TWDM lightwave network based on generalized de Bruijn digraph

A new model of generalized Steiner trees and 3coordinate systems

A model for network design

Nonlinear and mixedinteger optimization in chemical process network systems

Shortest networks on spheres