平成１２年度第１回KSMAP
平成１２年度第１回のKSMAPでは，京都大学の茨木先生にこれまでの研究生活を振り返っていただきました.
日時：５月１１日（木） １５：００ 〜 １７：３０
場所：京都大学 工学部8号館 共同6講義室
京都大学へのアクセス
講演題目と講演者
複合三角形消去問題に対する多項式時間近似スキーム
西田 幸弘 (京都大学情報学研究科) 講演要旨
通信サービス品質を差別化するためのトラヒック制御に関する考察
今川 裕人 (京都大学情報学研究科) 講演要旨
Locating Sources to Meet Flow Demands in Undirected Networks
新 浩治 ARATA Koji (大阪大学基礎工学研究科) 講演要旨
私の履歴書
茨木 俊秀 (京都大学情報学研究科) 講演要旨
講演要旨：
私の履歴書
茨木 俊秀 (京都大学情報学研究科)
KSMAP もいよいよ話題がなくなったのか、これまでの経歴とか研究とか
何でもよいから話して下さいという依頼を受けました。
この手の話しは定年退官のときかな、と思っていたので、いささか
あわてましたが、考えてみると定年まであと？年、その予行演習といった
心境です。去年、福嶋先生が同じタイトルで話しをされ、評判が良かったと
聞いています。柳の下に二匹目のどじょうがいるかどうかは分かりませんが、
暇な人は聞いてみて下さい。
複合三角形消去問題に対する多項式時間近似スキーム
西田 幸弘 (京都大学情報学研究科)
超大規模集積回路のレイアウト設計の初期段階に
フロアプランを決定する問題が現れる．
この問題は，モジュールと呼ばれる機能ブロックの形状制約や
各モジュール間の接続構造が与えられたときに，矩形チップ上
にモジュールを配置するための相対位置を定めるものである．
モジュール間の接続構造が平面グラフ$G$で表現されているとする．
ただし，$G$の節点はモジュールを表し，2つのモジュールが隣接関係を
持たなければならない場合に両者の節点を枝で結ぶ．
矩形モジュールのみを使った $G$ のフロアプランは矩形双対
と呼ばれるが，すべての平面グラフが
矩形双対をもつわけではない．すなわち，$G$ において，
内部に節点を含む三角形を複合三角形と呼ぶとき，
複合三角形を含む平面グラフ $G$ は矩形双対をもたない．
そこで，$G$から複合三角形を消去することを考える．
これは，複合三角形に使われている少なくとも1つの枝に
対して節点を挿入することにより可能となり，そのような操作を
加える枝集合を求める問題は複合三角形消去問題と呼ばれる．
この問題は枝に重み付いているとき，すべての複合三角形が消去される
ような重み最小の枝集合を求める問題はNP完全であることが知られている．
本研究では，この問題に対する多項式時間近似スキームを提案する．
通信サービス品質を差別化するためのトラヒック制御に関する考察
今川 裕人 (京都大学情報学研究科)
現在のインターネットにおけるパケット転送では，利用者に対して通信サービ
ス品質 (QoS) の保証を行わないベストエフォートサービスが大部分を占めて
いる．そこで利用者に対し QoS を保証する新しいサービス方策が期待されて
いる．利用者に低コストで QoS を保証するための方策の一つに
Differentiated Service がある．Differentiated Service では，パケットに
ラベル付けを行うことで幾つかのクラスに分け，クラス間の QoS を差別化す
る．現在までに，代表的なものとして Assured Service Scheme と Premium
Service Scheme が提案されている． Assured Service Scheme ではパケット
を確率的に棄却することによって，輻輳時における各クラスのスループットを
保証する．また，Premium Service Scheme ではクラス間に優先権を設け，各
クラスの伝送遅延時間を保証する．
これらスループットならびに遅延に関する差別化を実施した場合，インターネ
ット上では，これらの指標が組み合わされたサービスクラス，すなわち，スル
ープット，遅延の両方を保証するクラス，スループットを保証するクラス，遅
延を保証するクラス，ベストエフォートサービスを行うクラスが混在し，これ
らのクラス間で QoS を差別化する必要がある．しかし，このようなスループッ
トと遅延の両方を考慮したサービス方式についての研究はほとんど行われてい
ない．
本発表ではスループットならびに遅延に関して差別化された４種類のクラスに
対して差別化を行うサービス方式について考察した．特に，ルータのバッファ
管理に関して遅延に関するクラス毎に個別のバッファを用意する分離型と，全
てのクラスを１つのバッファへ収容する共有型の２種類を考えた．それぞれの
バッファ管理方式に対してモデル化を行い，システムの振舞いをマルコフ連鎖
で表現し，その定常状態確率を効率的に計算するアルゴリズムを提案した．次
に，提案したアルゴリズムに基づいて数値実験を行い，それぞれのバッファ管
理方式において，輻輳時のスループットならびに遅延のシステムを記述する各
パラメータに関する性質を考察した．その結果，共有型バッファ管理方式を用
いることにより，４つのクラスの過負荷時のスループットならびに遅延を差別
化できることが明らかになった．さらに，各クラスの負荷と目標となる輻輳時
のスループットならびに遅延が与えられたとき，共有型バッファ管理方式を用
いて，与えられた目標を達成するための制御パラメータの設定法を提案し，数
値実験によりその有効性を確認した．
Locating Sources to Meet Flow Demands in Undirected Networks.
新 浩治 (大阪大学基礎工学研究科)
This paper deals with the problem of finding a minimum-cost
vertex subset $S$ in an undirected network such that
for each vertex $v$ we can send $d(v)$ units of flow
from $S$ to $v$. Although this problem is NP-hard in general,
Tamura et al. have presented a greedy algorithm for
solving the special case with uniform costs on the vertices.
We give a simpler proof on the validity of the greedy algorithm
using linear programming duality and improve the running time bound
from $O(n^2M)$ to $O(nM)$, where $n$ is the number of vertices
in the network and $M$ denotes the time for max-flow computation in
the network with $n$ vertices and $m$ edges.
We also present an $O(n(m+n\log n))$ time algorithm
for the special case with uniform demands and arbitrary costs.
(Joint work with S. Iwata, K. Makino and S. Fujishige)
４０名の参加がありました．参加していただいた方々，
どうもありがとうございました．
柳浦 睦憲(yagiura@kuamp.kyoto-u.ac.jp)
<最終更新作成日時 2000年5月11日 >