Network Design
Connectivity and Facilities Location
Will be published approx. on 30. March 1998
Book
Hardback
461 pages
978-0-8218-0834-4 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Providence
United States
Target group
Professional and scholarly
Weight
1049 gr
ISBN-13
978-0-8218-0834-4 (9780821808344)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
Nearly linear time approximation schemes for Euclidean TSP and other geometric problems by S. Arora Differential greedy for the 0-1 equicut problem by R. Battiti and A. Bertossi Gradient-constrained minimal Steiner trees by M. Brazil, D. A. Thomas, and J. F. Weng The Steiner tree problem for terminals on the boundary of a rectilinear polygon by S.-W. Cheng Using Hadwiger numbers in network design by D. Cieslik Reducing the graphical Steiner problem with a sensitivity test by C. Duin A frequency assignment problem in cellular phone networks by A. Eisenblatter An optimal greedy algorithm for wavelength allocation in directed tree networks by T. Erlebach, K. Jansen, C. Kaklamanis, and P. Persiano A GRASP algorithm for the single source uncapacitated minimum concave-cost network flow problem by K. Holmqvist, A. Migdalas, and P. M. Pardalos Approximation results for the optimum cost chromatic partition problem by K. Jansen Approximating dense cases of covering problems by M. Karpinski and A. Zelikovsky Connected facility location problems by S. Guha and S. Khuller Constrained spanning tree problems: Approximate methods and parallel computation by N. Deo and N. Kumar Star, grid, ring topologies in facility location & network design by W.-J. Li and J. M. Smith Network improvement problems by S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, and S. S. Ravi Improved results on service-constrained network design problems by M. V. Marathe, R. Ravi, and R. Sundaram A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem by R. A. Murphey, P. M. Pardalos, and L. Pitsoulis A generalized threshold algorithm for the shortest path problem with time windows by W. B. Powell and Z.-L. Chen A case study of derandomization methods for combinatorial approximation algorithms by J. D. P. Rolim and L. Trevisan A chunking based genetic algorithm for the Steiner tree problem in graphs by S. Voss and K. Gutenschwager A new exact algorithm for rectilinear Steiner trees by D. M. Warme A scalable TWDM lightwave network based on generalized de Bruijn digraph by P.-J. Wan and A. Pavan A new model of generalized Steiner trees and 3-coordinate systems by J. F. Weng A model for network design by R. Wessaly Nonlinear and mixed-integer optimization in chemical process network systems by C. S. Adjiman, C. A. Schweiger, and C. A. Floudas Shortest networks on spheres by M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald.