DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 1998; 461 pp; hardcover Volume: 40 ISBN10: 0821808346 ISBN13: 9780821808344 List Price: US$101 Member Price: US$80.80 Order Code: DIMACS/40
 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 17 were copublished 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  S. Arora  Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
 R. Battiti and A. Bertossi  Differential greedy for the 01 equicut problem
 M. Brazil, D. A. Thomas, and J. F. Weng  Gradientconstrained minimal Steiner trees
 S.W. Cheng  The Steiner tree problem for terminals on the boundary of a rectilinear polygon
 D. Cieslik  Using Hadwiger numbers in network design
 C. Duin  Reducing the graphical Steiner problem with a sensitivity test
 A. Eisenblätter  A frequency assignment problem in cellular phone networks
 T. Erlebach, K. Jansen, C. Kaklamanis, and P. Persiano  An optimal greedy algorithm for wavelength allocation in directed tree networks
 K. Holmqvist, A. Migdalas, and P. M. Pardalos  A GRASP algorithm for the single source uncapacitated minimum concavecost network flow problem
 K. Jansen  Approximation results for the optimum cost chromatic partition problem
 M. Karpinski and A. Zelikovsky  Approximating dense cases of covering problems
 S. Guha and S. Khuller  Connected facility location problems
 N. Deo and N. Kumar  Constrained spanning tree problems: Approximate methods and parallel computation
 W.J. Li and J. M. Smith  Star, grid, ring topologies in facility location & network design
 S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, and S. S. Ravi  Network improvement problems
 M. V. Marathe, R. Ravi, and R. Sundaram  Improved results on serviceconstrained network design problems
 R. A. Murphey, P. M. Pardalos, and L. Pitsoulis  A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem
 W. B. Powell and Z.L. Chen  A generalized threshold algorithm for the shortest path problem with time windows
 J. D. P. Rolim and L. Trevisan  A case study of derandomization methods for combinatorial approximation algorithms
 S. Voß and K. Gutenschwager  A chunking based genetic algorithm for the Steiner tree problem in graphs
 D. M. Warme  A new exact algorithm for rectilinear Steiner trees
 P.J. Wan and A. Pavan  A scalable TWDM lightwave network based on generalized de Bruijn digraph
 J. F. Weng  A new model of generalized Steiner trees and 3coordinate systems
 R. Wessäly  A model for network design
 C. S. Adjiman, C. A. Schweiger, and C. A. Floudas  Nonlinear and mixedinteger optimization in chemical process network systems
 M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald  Shortest networks on spheres
