セミナー

• 現実社会に現れる多くの問題が組合せ最適化問題として定式化できる．そのような問題はNP困難であることが多く，規模の大きい問題例を厳密に解くことは困難である．そこで，実践的な解決策として，最適性の保証はなくとも，良い解を速く求めようとする手法が研究されている．代表的なものとして，欲張り法や局所探索法などの基本戦略があり，また，それらを高度に組み合わせるなどの方法によってより良い解を得ようとするメタ戦略がある．本講演では，そのような手法に基づいて効率的なアルゴリズムを構築するために行ってきた研究について紹介する．

  2023.02.06 Mon. 10:00-12:00

  第35回セミナー・勉強会
  話者：柳浦 睦憲（名古屋大学，招待講演） 題目：組合せ最適化問題に対する実践的解法 概要：
• あみだくじは，1 から n を表す n 本の縦線と，縦線 2 本の間を結ぶ横棒からなる．横棒を，その横棒が結ぶ２本の縦線のラベルを交換する互換とみなすことで，あみだくじ (つまり横棒と縦線からなるネットワーク) は置換を表すことになる．横棒を比較器とみてソーティングネットワーク (sorting network) として研究されることも多く，特に，隣り合う縦線 2 本の間の互換のみに横棒を制限した場合には primitive sorting network と呼ばれる．菱形タイリングは，辺の長さが同じ菱形を，隙間なく重なりなく敷き詰めたものである．本講演では，あみだくじと菱形タイリングの関係について説明し，逆探索や ZDD (Zero-Suppressed Binary Decision Diagrams; 零抑制型二分決定グラフ) による列挙や，その後の広がりについて述べる．

  2023.01.16 Mon. 10:00-12:00

  第34回セミナー・勉強会
  話者：堀山 貴史（北海道大学，招待講演） 題目：あみだくじと菱形タイリングの列挙 概要：
• 発表者が学生時代から十数年来取り組んでいる分散計算理論がどのような分野であるのか，最近の研究事例2つを通してご紹介いたします．具体的には，
   (i) 個体群モデルにおけるリーダ選挙問題，および，
   (ii) モバイルエージェントによるビザンチン集合問題
  について，問題設定やこれまでに発見されたいくつかのアルゴリズムをご解説いたします．

   

  個体群モデルとは，消極移動（自分で制御できない移動）を絶えず行う微小で計算資源に乏しい計算機で構成するネットワークを表現する分散計算のモデルです．このモデルは2004年にAngluinらによって提案されて以来，盛んに研究が行われてきました．とりわけ，リーダ選挙問題と多数決問題のふたつは大変良く研究されている問題で，前者については，2020年にBerenbrinkらによってついに時間最適かつ空間最適なアルゴリズムが発見されました．本講演では，このリーダ選挙問題について解説します．

   

  モバイルエージェントとは，計算機ネットワーク上を自律的に移動するソフトウェアのことです．ネットワーク上に存在するすべてのエージェントをひとつの計算機に集める集合問題は基本的かつ重要な問題で，分散計算理論のコミュニティでは大変よく研究されています．本講演では，ネットワーク上の一部のエージェントが任意の敵対的な行動を取る場合にも正常なエージェントをひとつの計算機に集合させることを目的としたビザンチン集合問題を紹介します．
   

  2022.12.05 Mon. 10:00-12:00

  第33回セミナー・勉強会
  話者：首藤 裕一（法政大学，招待講演） 題目：分散計算理論の世界 概要：
• 電力・エネルギー分野において，私は再生可能エネルギー電源の主力電源化を目指し，安全性と安定供給・経済性・環境保全を確保することを大前提として，最大限導入するための仕組みについて研究している．再生可能エネルギー電源を増加させることの課題の一つは，電力システムから供給される電力の品質劣化であり，社会生活に悪影響を及ぼす可能性がある．本講演では，再生可能エネルギー電源に起因する電力品質劣化のメカニズムと対策について述べ，再生可能エネルギー電源の導入可能量を拡大するための研究について紹介する．

  2022.11.28 Mon. 10:00-12:00

  第32回セミナー・勉強会
  話者：飯岡 大輔（中部大学，B01班） 題目：再生可能エネルギーを主体とする電力システムの構築 概要：
• 離散時間論理型有限力学系モデル（DT-BFDS）は、力学系モデル（dynamical systems）に離散時間で動作する、頂点が一定でその状態が論理値であるという制限を加えて、単純化したものである。DT-BFDSは離散時間で変化する社会現象、あるいはタンパク質間や遺伝子間の相互作用ネットワークのシミュレーションの道具として使われており、また、DT-BFDSの性質に関する問題が計算量理論を用いて研究されている。DT-BFDSは従来決定性のモデルであり、非決定的な動きをするモデルの体系はまだ確立されていない。確率的なモデルを使用したDT-BFDSモデルが幾つか提案されているが、そこに於ける確率的選択の使用は、初期値の生成など、動作の一部に限られている。

   

  本研究の目的は、このDT-BFDSに不確定要素を導入する方法を提案し、それによって生じるモデルの計算力を調べる事である。ここでは二つの独立した方式を不確定性の導入方を提案する。その一つは、状態の更新に使われる関数に、頂点毎に選択肢を与える事であり、もう一つは、頂点が各時刻において順々に状態の更新を行うと仮定し、その順序に選択肢を与える事である。この二つの方式をそれぞれ何種類かに分け、それらを組み合わせる事により、多岐のモデルが定義できる。本講演では、この試みの初期の結果を発表する。まず、モデルの多項式時間埋め込み可能性の概念を定義し、このようなモデルの相互関係を立証する。さらには、いくつかのモデルの計算能力を到達可能性問題の計算量理論的分析により、明らかにする。

  2022.11.14 Mon. 10:00-12:00

  第31回セミナー・勉強会
  話者：荻原 光徳（マイアミ大学，招待講演） 題目：離散時間論理型有限力学系の不確定性モデル 概要：
• k彩色遷移問題とは，無向グラフとその２つのk頂点彩色が与えられた際に，片方の彩色からもう片方の彩色へ，k頂点彩色であることを保ったまま，一度に一つの頂点の色を変えながら遷移することが可能であるか否かを判定する問題である．本講演では，ある色からある色へは直接変えることが出来ないという遷移可能性制約を考える．この制約は色を頂点とし，直接変えることのできる色の順序対を辺とする有向グラフにより与えることができる．本講演では，この有向グラフが有向サイクルであるかマルチツリーのある部分クラスに含まれる場合に，k彩色遷移問題が線形時間で解けることを示す．本講演は，藤井宗一郎氏，岩政勇仁氏，鈴木顕氏との共同研究に基づく．

  2022.10.31 Mon. 10:00-12:00

  第30回セミナー・勉強会
  話者：木村 慧（九州大学，招待講演） 題目：遷移可能性制約をもつ彩色遷移問題 概要：
• オンライン二部マッチング問題は，二部グラフの片側の頂点がひとつずつやってくるときに，できるだけ大きなサイズのマッチングを求める問題である．この問題は検索広告の割り当て，ライドシェアリング，クラウドソーシングなどさまざまな応用をもつ．本講演では，オンライン二部マッチングに，これらの応用を動機とした制約を課した問題を考え，定数競合比を達成するアルゴリズムを提案する．本講演は，澄田範奈氏，伊藤伸志氏，竹村慧氏，波多野大督氏，福永拓郎氏，河原林健一氏との共同研究に基づく．

  2022.10.17 Mon. 10:00-12:00

  第29回セミナー・勉強会
  話者：垣村 尚徳（慶應義塾大学，C01班） 題目：制約付きのオンライン二部マッチング 概要：
• 本講演では，学術変革(B)B01班で開発中の組合せ遷移問題を解くPythonライブラリを紹介する．reconfillion（仮）は部分グラフ列挙ライブラリである graphillion を基にして様々な組合せ遷移問題を解くライブラリであり，graphillion で表現可能な対象に関する組合せ遷移問題を解くことが可能である．reconfillion の中で用いられているアルゴリズムも紹介する．

  2022.07.25 Mon. 15:00-17:00

  第28回セミナー・勉強会
  話者：川原 純（京都大学，B01班） 題目：Reconfillion: 組合せ遷移ソルバー 概要：
• 各々が目的地をもつ複数エージェントをスムーズに移動させる技術はファクトリーオートメーションやビデオゲーム，ドローンショーなど，多方面に魅力的な応用がある．本講演ではグラフ上のエージェント群に衝突のない経路を割当てるマルチエージェント経路計画（Multi-Agent Path Finding; MAPF）を中心に，連続空間でのプランニングやロボット群での実行手法を取扱い, 移動エージェント群の制御手法を概観する．

  2022.07.11 Mon. 15:00-17:00

  第27回セミナー・勉強会
  話者：奥村 圭祐（東京工業大学，招待講演） 題目：エージェント群のナビゲーション 概要：
• 有限な離散集合上に定義される統計モデルの当てはまりを評価するための，マルコフ連鎖を利用したシミュレーション手法を紹介する．既約なマルコフ連鎖を構成するための推移基底（マルコフ基底）は代数的に特徴づけられ，多項式環のグレブナー基底の理論を用いて計算することができる．本講演では，この問題を理解するために必要な統計学と代数学の理論を概説し，講演者の関連する研究を紹介する．

  2022.06.13 Mon. 15:00-17:00

  第26回セミナー・勉強会
  話者：青木 敏（神戸大学，招待講演） 題目：マルコフ連鎖モンテカルロ法のための計算代数 概要：