A01班 班会議

===============================================================
  科研費特定領域研究「新しいパラダイムとしてのアルゴリズム工学」
       A01班(離散最適化アルゴリズム)　 班会議のお知らせ
===============================================================

                        ---- A01班以外の方の参加も歓迎します．

◎ 日時：平成11年12月21日(火) 10:00 - 16:20
◎ 場所：大阪大学吹田キャンパス　医学部　銀杏会館

 ☆　銀杏会館への交通案内は、以下のURLをご参照下さい。
 　吹田キャンパスへの案内(http://www.osaka-u.ac.jp/annai/campus/access.html)
 　吹田キャンパス建物の配置図(http://www.osaka-u.ac.jp/annai/campus/suita.html)
 　    会場は、医学部銀杏会館(番号22)。
 ☆　標準ルート：地下鉄御堂筋線の終点，千里中央で下車．
　　　　阪急バス（阪大本部前行、または茨木美穂ヶ丘行）阪大本部前 下車.
　　　　徒歩数分で銀杏会館． 新大阪 から 銀杏会館 まで，約1時間。
　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　｜｜×医学部銀杏会館　
　　　　　　　　　　　　　テニスコート○｜｜
　　　　　　　　　　　＝＝＝＝＝＝＝＝　｜　○RI総合センター　
　　　　　　レーザー核融合研究センター○｜｜○保全科学研究センター
　　　　　　　　　　　　阪大本部バス停×｜｜○福利会館
　　　　　　　　　　　　＝＝＝＝＝＝＝＝　　＝＝＝＝＝
　　その他詳しい経路説明を最後に添付します．


◎ 講演者と講演タイトル：

10:00 - 10:50  牧野和久（大阪大学大学院 基礎工学研究科） 
        「ハイパーグラフの部分横断と多重横断について」
11:10 - 12:00  土村展之 (LOGOPT)
        「データベース登録状況報告」
12:00 - 12:40  Business Meeting
14:20 - 15:10  市川周一  (豊橋技術科学大学 知識情報工学系)
        「並列計算における静的負荷分散」
15:30 - 16:20  藤江哲也  (神戸商科大)
        「線形化による半正定値計画緩和と線形計画緩和」

◎ 講演アブストラクト：

牧野和久：ハイパーグラフの部分横断と多重横断について
　ハイパーグラフの極小横断(Minimal transversal)を列挙することが（入力長と
　出力長の）多項式時間で可能かどうかは有名な未解決問題である．この問題は，
　単に数学的に面白いばかりでなく，分散システムのコテリー理論や人工知能にお
　ける推論問題といった実用的な問題にも密接に関連している．
　本研究では，横断の概念を一般化させた部分横断，多重横断を導入し，ハイパー
　グラフの極小部分横断（あるいは，極小多重横断）を列挙する問題が上記の問題
　に多項式時間還元可能であることを示す．また，部分，多重横断といった概念と
　知識発掘(data mining)における frequent set などとの関係を示す．
　さらに，ここで用いられた証明手法が単調多面体におけるファセット数の下限を
　与えることも示す．

土村展之：データベース登録状況報告
　全体会議以降、ご連絡いただいた web デモと、パッケージプログラムについて
　御紹介します。多少 技術的な内容に踏み込んで、発表させていただきます。

市川 周一： 並列計算における静的負荷分散
　並列計算における静的負荷分散は、古くから“マルチプロセッサスケジューリン
　グ問題”として単純化され研究されてきた。単純化された問題ですら計算困難で
　あるが、現実的な並列処理では通信時間やデータ分割など多くの要素を考慮しな
　ければ役に立たない。偏微分方程式の並列・分散処理に関して問題点を検討する。

藤江哲也： 線形化による半正定値計画緩和と線形計画緩和
　Lovasz and Schrijverは、0-1整数計画問題に対する半正定値計画問題
　(行列変数に関する最適化問題)、および連続緩和よりも強力な線形計画問題による
　緩和を提案した。また、Goemans and Williamsonは、最大カット問題に対し、半正
　定値計画緩和を用いた画期的な近似解法を提案した。
　半正定値計画緩和は、これらを契機として注目されるようになったといえる。
　半正定値計画緩和を導く方法は複数存在するが、線形化とよばれる方法は、
　Lovasz and Schrijverの方法に関連するもので、0-1整数計画・組合せ最適化問題
　を含む広いクラスの問題に対して半正定値計画緩和・線形計画緩和を導くことがで
　きる。その結果、Balas, Ceria and Cornuejolsによる、0-1整数計画問題に対する
　Lift-and-Projectカットや、Sheraliらによる、Reformulation-Linearization 
　Technique, Reformulation-Convexification Techniqueがこの枠組で理解できるよう
　になる。
　本発表では、線形化および半正定値計画緩和・線形計画緩和の導出方法と基本性質
　を与える。さらに、個々の問題に適用して得られる結果について概観する。



◎ 銀杏会館(阪大吹田キャンパス、医学部)への経路説明

１.(京阪本線)淀屋橋で、(地下鉄御堂筋)淀屋橋に乗り換え、(御堂筋は江坂で大
阪北急行に連絡)終点千里中央で下車し、(阪急バス、毎時4〜6便)阪大本部前行、ま
たは茨木美穂ヶ丘行に乗り、阪大本部前で下車してください。さらに銀杏会館まで徒
歩数分です。京阪淀屋橋から銀杏会館まで、1時間強ぐらいです。
 
２.(大阪モノレール)千里中央で門真市行(毎時5便)に乗り、万博記念公園駅で乗
り換え、(モノレール彩都線、毎時2〜3便、待ち時間2分〜24分)阪大病院前で下車し
、銀杏会館まで、徒歩で約15分です。(注意：モノレールの千里中央駅は、大阪北急
行・御堂筋の同駅から歩いて5分離れています。)モノレール千里中央から銀杏会館ま
で、40分から約1時間です。

３.(阪急京都線)茨木で下車し、(近鉄バス、毎時4〜6便)阪大本部前行に乗り、終
点阪大本部前で下車し、銀杏会館まで徒歩数分です。阪急茨木から銀杏会館まで、(
交通渋滞がない場合)約30分です。あるいは、(阪急京都線)南茨木で、(モノレール)
南茨木に乗り万博記念公園駅まで行き、モノレール彩都線（説明２)に乗り換えるか
、またはモノレールで千里中央まで行き、阪急バス（説明１）を利用してください。

４．(新幹線)新大阪で下車し、(地下鉄御堂筋)新大阪から終点千里中央まで行き
、後は阪急バス(説明１)あるいは、モノレール(説明２)を利用してください。阪急バ
ス経由では、新大阪から銀杏会館まで約1時間です。あるいは、(新幹線)京都で下車
し、乗り換えて(東海道本線)茨木まで行き、後は近鉄バス(説明３)を利用してくださ
い。JR京都駅から銀杏会館まで(交通渋滞がない場合)約1時間です。

５.(飛行機)大阪空港(伊丹)から、モノレールが利用できます。大阪空港から千里
中央まで13分、さらに6分で万博記念公園駅(説明２)に着きます。千里中央からは阪
急バス(説明１)も利用できます。あるいは関西空港からは、南海線で難波まで行き、
(地下鉄御堂筋)難波から千里中央まで行き阪急バス(説明１)を利用するか、JR線で関
西空港から大阪まで行き、(地下鉄御堂筋)梅田で乗り換え千里中央まで行き、阪急バ
ス(説明１)またはモノレール(説明２)を利用してください。



◎「新しいパラダイムとしてのアルゴリズム工学」のホームページ:
    http://www.kuamp.kyoto-u.ac.jp/labs/or/tokutei98/

◎ 連絡先： 
  プログラムについて：
         〒606-XXXX  京都市YYYY
         京都大学YYYYYYYY
         室田 一雄 
         EMAIL: murota＠hoge.kyoto-u.ac.jp
         TEL: 075-YYY-XXXX

  会場について：
         〒565-XXXX　吹田市YYYYYY
         大阪大学大学院YYYY研究科ZZZZZZ学専攻
         齋藤 誠慈
         E-mail：saito-se＠hoge.osaka-u.ac.jp
         TEL:06-YYYY-YYYY FAX:06-YYYY-NNNN