Abstract: The network design problem (NDP) is a well known problem which can be applied to many different types of networks. It was well investigated applied to computer communications networks during the time of Internet development. Today it is again very actual applied mostly to the dynamic wireless networks (MANET – mobile ad hoc networks). The network design problem is an NP-hard problem which involves topology selection (subset of possible links) and routing determination (paths for the offered traffic). Capacity assignment is usually treated as a 0-1 problem and as such included it in the topology problem. This does not make the network design problem easier, just the opposite, it moves optimization from continuous to integer. The goal is to minimize the cost which can be a combination of the link costs and delay penalties, under possible additional constraints. Such hard combinatorial graph problems are often treated by evolutionary metaheuristics. In many cases better results and faster convergence are achieved by hybrid algorithms where some local searcher that utilizes particular knowledge about the corresponding problem is included. Here we propose and analyze a computationally feasible heuristic algorithm which excludes underutilized links by a version of flow-deviation method. A simplified queuing model is developed for cost function estimate. Some theoretical results are also established that direct initial approximation. Proposed algorithm can dynamically be adjusted for faster or better results. It is implemented and computes a good solution that is robust with respect to often required dynamic changes of the cost function.

Brief Biography of the Speaker:
Milan Tuba received B. S. in Mathematics, M. S. in Mathematics, M. S. in Computer Science, M. Ph. in Computer Science, Ph. D. in Computer Science from University of Belgrade and New York University. From 1983 to 1994 he was in the U.S.A. first as a graduate student and teaching and research assistant at Vanderbilt University in Nashville and Courant Institute of Mathematical Sciences, New York University and later as an Assistant Professor of Electrical Engineering at Cooper Union Graduate School of Engineering, New York. During that time he was the founder and director of Microprocessor Lab and VLSI Lab, leader of scientific projects and supervisor of many theses. From 1994 he was Associate professor of Computer Science and Director of Computer Center at University of Belgrade, Faculty of Mathematics, and from 2004 also a Professor of Computer Science and Dean of the College of Computer Science, Megatrend University Belgrade. He was teaching more than 20 graduate and undergraduate courses, from VLSI Design and Computer Architecture to Computer Networks, Operating Systems, Image Processing, Calculus and Queuing Theory. His research interest includes mathematical, queuing theory and heuristic optimizations applied to computer networks, image processing and combinatorial problems. He is the author of more than 90 scientific papers and a monograph. He is coeditor or member of the editorial board or scientific committee of number of scientific journals and conferences. Member of the ACM since 1983, IEEE 1984, New York Academy of Sciences 1987, AMS 1995, SIAM 2009. Participated in many WSEAS Conferences with plenary lectures and articles in Proceedings and Transactions.