DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Forty
TITLE: "Network Design: Connectivity and Facilities Location"
EDITORS: Panos M. Pardalos and Dingzhu Du.

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

PREFACE


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.


TABLE OF CONTENTS


Foreword						  xi

Preface							xiii

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

Differential greedy for the 0-1 equicut problem
    R. Battiti and A. Bertossi				   3

Gradient-constrained minimal Steiner trees
    M. Brazil, D. A. Thomas, and J. F. Weng		  23

The Steiner tree problem for terminals on the boundary 
  of a rectilinear polygon
    Sui-Wing Cheng					  39

Using Hadwiger numbers in network design
    D. Cieslik						  59

Reducing the graphical Steiner problem with a 
  sensitivity test
    Cees Duin						  79

A frequency assignment problem in cellular phone 
  networks
    Andreas Eisenblatter				 109

An optimal greedy algorithm for wavelength allocation 
  in directed tree networks
    Thomas Erlebach, Klaus Jansen, 
    Christos I. Kaklamanis, and Pino Persiano		 117

A GRASP algorithm for the single source uncapacitated 
  minimum concave-cost network flow problem
    Kristina Holmqvist, Athanansios Migdalas, and 
    Panos M. Pardalos					 131

Approximation results for the optimum cost chromatic 
  partition problem
    Klaus Jansen					 143

Approximating dense cases of covering problems
    Marek Karpinski and Alexander Zelikovsky		 169

Connected facility location problems
    Sudipto Guha and Samir Khuller 			 179

Constrained spanning tree problems: Approximate 
  methods and parallel computation
    Narsingh Deo and Nishit Kumar			 191

Star, grid, ring topologies in facility location & 
  network design
    Wu-Ji Li and J. MacGregor Smith 			 219

Network improvement problems
    Sen O. Krumke, Madhav V. Marathe, 
    Hartmut Noltemeier, R. Ravi, and S.S. Ravi		 247

Improved results on service-constrained network 
  design problems
    Madhav V. Marathe, R. Ravi, and R. Sundaram		 269 

A greedy randomized adaptive search procedure for the 
  multitarget multisensor tracking problem
    R. A. Murphey, P. M. Pardalos, and L. S. Pitsoulis	 277

A generalized threshold algorithm for the shortest 
  path problem with time windows
    Warren B. Powell and Zhi-Long Chen			 303

A case study of de-randomization methods for 
  combinatorial approximation algorithms
    Jose D. Rolim and Luca Trevisan			 319

A chunking based genetic algorithm for the Steiner 
  tree problem in graphs
    Stefan Voß and Kai Gutenschwager			 335

A new exact algorithm for rectilinear Steiner trees
    David M. Warme					 357

A scalable TWDM lightwave network based on 
  generalized de Bruijn digraph
    Peng-Jun Wan and A. Pavan				 397

A new model of generalized Steiner trees and 
  3-coordinate systems
    J. F. Weng						 415

A model for network design
    Roland Wessaly					 425

Nonlinear and mixed-integer optimization in chemical 
  process network systems
    C. S. Adjiman, C. A. Schweiger, and C. A. Floudas	 429

Shortest networks on spheres
    M. Brazil, J. H. Rubinstein, D. A. Thomas, 
    J. F. Weng, and N. C. Wormald			 453
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.