**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 40;
1998;
461 pp;
Hardcover

MSC: Primary 03; 90; 68;

**Print ISBN: 978-0-8218-0834-4
Product Code: DIMACS/40**

List Price: $108.00

AMS Member Price: $86.40

MAA Member Price: $97.20

**Electronic ISBN: 978-1-4704-3998-9
Product Code: DIMACS/40.E**

List Price: $101.00

AMS Member Price: $80.80

MAA Member Price: $90.90

# Network Design: Connectivity and Facilities Location

Share this page *Edited by *
*Panos M. Pardalos; Dingzhu Du*

A co-publication of the AMS and DIMACS

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 multiple-connected Steiner network, independent flow problem,
and subset-interconnection 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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Readership

Graduate students, research mathematicians, computer scientists and operations researchers working on network design problems.

# Table of Contents

## Network Design: Connectivity and Facilities Location

- Cover Cover11
- Title page v6
- Quotation vii8
- Contents ix10
- Foreword xi12
- Preface xiii14
- Nearly linear time approximation schemes for Euclidean TSP and other geometric problems 116
- Differential greedy for the 0–1 equicut problem 318
- Gradient-constrained minimal Steiner trees 2338
- The Steiner tree problem for terminals on the boundary of a rectilinear polygon 3954
- Using Hadwiger numbers in network design 5974
- Reducing the graphical Steiner problem with a sensitivity test 7994
- A frequency assignment problem in cellular phone networks 109124
- An optimal greedy algorithm for wavelength allocation in directed tree networks 117132
- A GRASP algorithm for the single source uncapacitated minimum concave-cost network flow problem 131146
- Approximation results for the optimum cost chromatic partition problem 143158
- Approximating dense cases of covering problems 169184
- Connected facility location problems 179194
- Constrained spanning tree problems: Approximate methods and parallel computation 191206
- Star, grid, ring topologies in facility location & network design 219234
- Network improvement problems 247262
- Improved results on service-constrained network design problems 269284
- A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem 277292
- A generalized threshold algorithm for the shortest path problem with time windows 303318
- A case study of de-randomization methods for combinatorial approximation algorithms 319334
- A chunking based genetic algorithm for the Steiner tree problem in graphs 335350
- A new exact algorithm for rectilinear Steiner trees 357372
- A scalable TWDM lightwave network based on generalized de Bruijn digraph 397412
- A new model of generalized Steiner trees and 3-coordinate systems 415430
- A model for network design 425440
- Nonlinear and mixed-integer optimization in chemical process network systems 429444
- Shortest networks on spheres 453468
- Back Cover Back Cover1479