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.
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.
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