第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 of 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 network optimization problems. In this talk we shall focus on algorithmic approaches to certain path problems called QoS (Quality of Service) 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 route selection 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.

講演報告:
 講演後は多数の質問が寄せられ,活発な質疑応答が行われた. 講師Thulasiraman教授からの回答に加えて参加者の方からも貴重なコメントを頂くなど, 大変充実した内容であった.

参加者:約30名
報告者:西関 隆夫
東北大学 大学院情報科学研究科
〒980-8579 仙台市青葉区荒巻字青葉6-6-05
TEL: 022-795-7162 FAX: 022-263-9301