The objective of this research is to develop new algorithmic techniques to compute efficiently near optimal solutions to a number of NP-hard graph problems arising in network-design. A partial list of problems studied include: (a) problems in Euclidean setting including the traveling salesman problem; (b) designing low-congestion networks for multicommodity flow; (c) computing broadcast-trees for fast dissemination of information in networks; (d) finding low-cost networks of specified connectivity. The goal is to develop algorithms which not only generate good solutions, but are also practically feasible. Algorithms developed are both implemented and tested.
