Network optimization refers to the class of optimization problems defined on graphs and networks. These problems occur in a wide variety of applications, in particular, VLSI CAD and Telecommunication Networks. Path and flow algorithms play a fundamental role in the study of network optimization problems. These algorithms, while important in their own right, also serve as building blocks in the design of algorithms for complex networkoptimization problems. In this talk we shall focus on algorithmic approaches to certain path problems called QoS (Quality ofService) path problems that require etermining minimum cost paths satisfying a quality of service guarantee with respect to one or more metrics.
There are two classes of QoS path problems--- single routeselection and selection of a set of disjoint paths between a source and a destination. These problems are NP-hard and hence in the literature heuristics and approximation algorithms have been extensively studied. Whereas heuristics provide acceptable solutions with performance guarantees, approximation algorithms provide solutions with user specified performance guarantees. In this talk we shall present two classes of heuristic approaches ( including our own ) for both these problems. These are based on Lagrangian dual method and the primal simplex method of linear programming. We shall also briefly review current research trends in the design of approximation algorithms as well as algorithms for path problems under inaccurate information.