第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 NPhard 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名
 報告者：西関 隆夫
 東北大学 大学院情報科学研究科
 〒9808579 仙台市青葉区荒巻字青葉6605
 TEL: 0227957162 FAX: 0222639301