第320回研究講演会開催案内


情報処理学会東北支部 第320回研究講演会開催案内
日時: 2005年5月20日(金)15:00〜16:00
会場: 東北大学工学部電気情報系 201講義室
講師:Dr. Krishnaiyan Thulasiraman
Professor and Hitachi Chair in Computer Science
School of Computer Science
University of Oklahoma
USA
演題:QoS Path Problems in Communication Networks :
Approximation Algorithms Based on
Mathematical Programming Techniques

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

問合せ先:
西関隆夫