アブストラクト:
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.