C01

• 野崎 雄太 (広島大学, C01班) が，電子情報通信学会コンピュテーション研究会にて招待講演を行います．

   

  2023年3月2日 (木) 13:30-14:30

  野崎 雄太 「組合せ遷移におけるトポロジーの視点」

   

  参加お申込み等の詳細は，研究会のWebサイトをご覧ください．

  電子情報通信学会コンピュテーション研究会

  2023.03.02 Thu.

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

  2022.10.17 Mon. 10:00-12:00

  第29回セミナー・勉強会
  話者：垣村 尚徳（慶應義塾大学，C01班） 題目：制約付きのオンライン二部マッチング 概要：
• 本発表では，各点が接続する辺に対する選好を持つ二部グラフ上のマッチング問題を考える．特に，安定性とパレート効率性と呼ばれる二つの性質を満たすマッチングであるパレート安定マッチングに対するアルゴリズムを考える．本発表では，講演者の最近の成果を含め，パレート安定マッチングに関する成果を，組合せ遷移的な視点も交えながら紹介する．

  2022.04.25 Mon. 15:00-17:00

  第23回セミナー・勉強会
  話者：神山 直之（九州大学，C01班） 題目：パレート安定マッチング 概要：
• 小林 佑輔 (京都大学，C01班) が，電子情報通信学会コンピュテーション研究会にて，C01班の研究成果に関して招待講演を行います．

   

  2022年3月6日 (日) 13:30-14:30

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki,
  Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

  (SODA 2022 採択論文)

   

  参加お申込みは，研究会のWebサイトをご覧ください．

  電子情報通信学会コンピュテーション研究会

   

  2022.03.06 Sun.

  電子情報通信学会コンピュテーション研究会にて招待講演
  話者： 題目： 概要：
• グラフの向き付けとは，無向グラフの各辺に向きを付けて有向グラフを得ることをいい，組合せ最適化やグラフ理論の分野で盛んに研究されているトピックである．本講演では，連結度制約を保ちながら向き付けの辺の向きを1本ずつ変更していく，「グラフ向き付けの遷移」に関する講演者らの最新の成果について紹介する．我々の主結果は，「2k辺連結無向グラフの任意の向き付けに対して，うまく辺の向きを1本ずつ変更していくことで辺連結度を単調に増加させ，最終的にk辺連結向き付けを得ることができる」というものである．これは，古典的な Nash-Williams の定理を強めた結果であり，k辺連結向き付けのフリップ・グラフの連結性を議論する際にも有用である．

  なお，この成果は本プロジェクトメンバーとの共同研究に基づくものであり，SODA2022で発表予定である．

  2021.11.11 Thu. 10:00-12:00

  第17回セミナー・勉強会
  話者：小林 佑輔（京都大学，C01班） 題目：連結度制約付きグラフ向き付けの遷移 概要：
• 講演者はトポロジー（位相幾何学）を専門とし，図形や空間の性質を研究している．トポロジーに由来する発想や道具は数学全体に波及し，最近では数学以外でも「トポロジカル」という形容詞を目にする機会が増えた．トポロジーのおもしろさの1つは，幾何的な入力から群などの代数的な出力を得る過程にある．本講演では具体的な問題を題材として，その考え方や捉え方をお伝えしたい．また講演者が組合せ遷移のプロジェクトに参加して興味を持った話題にも言及する予定である．

  2021.07.26 Mon. 10:00-12:00

  第14回セミナー・勉強会
  話者：野崎 雄太（広島大学，C01班） 題目：トポロジーの視点 概要：
• 制約充足問題 (Constraint Satisfaction Problem, CSP) とは，与えられた制約を全て充足する変数割当が存在するか否かを判定する問題である．CSP は一般的に NP 完全であるが，制約に現れる関係に制限を加えることで多項式時間可解な部分クラスが得られることもある．Feder-Vardi は 1998 年に，関係に制限を加えることで得られる問題は P か NP 完全のどちらかであるという予想（二分予想）を提唱した．この予想は長らく未解決であったが，2017 年に Bulatov と Zhuk により独立に肯定的に解決された．本講演では，二分予想の証明において重要な役割を果たした代数的アプローチについて概説する．

  2021.06.07 Mon. 10:00-12:00

  第11回セミナー・勉強会
  話者：岩政 勇仁（京都大学，C01班） 題目：制約充足問題に対する代数的アプローチ 概要：
• 辺着色されたグラフとは，グラフの各辺に色が1色ずつ塗られたグラフのことである．本講演では，近年研究が進んでいる，辺着色されたグラフから特定のグラフ，例えば，properly coloredなハミルトン閉路やproperly coloredな全域木，を見つけるという研究とその研究に関する講演者の成果を述べる．また，辺着色されたグラフにおけるこのような研究とマトロイドの関係性についても議論する．その一例として，Rotaのcolorful予想と辺着色されたグラフの辺分割の関係性について議論する．
   

  2021.04.26 Mon. 10:00-12:00

  第08回セミナー・勉強会
  話者：前澤 俊一（電気通信大学，C01班） 題目：辺着色グラフにおける特定の性質を満たす部分グラフ 概要：
• どの隣接2辺も異なる色となるように辺に色を割り当てることをそのグラフの辺彩色といい，特に高々 3 色しか使わないとき 3-辺彩色という．3-辺彩色において，2色で塗られた閉路を1つ選び，その閉路上の色を取り換えることで新しい3-辺彩色が得られる．この操作はケンペによって四色定理の証明のために導入されたもので，現在でも関連問題に対して有力な操作として扱われているものである． 本講演では，3-正則グラフ (どの頂点にも 3本の辺が接続するグラフ) における 3-辺彩色全体の集合に上の遷移を導入し，その到達可能性について議論する．

  2021.02.12 Fri. 15:00-17:00

  第06回セミナー・勉強会
  話者：小関 健太（横浜国立大学，C01班） 題目：3-正則グラフにおける3-辺彩色のケンペ鎖による遷移 概要：
• 「組合せ遷移は，離散数学において伝統的に研究されてきた」という立場で，離散数学において どのような組合せ遷移問題が考えられてきたか，紹介する．また，その文脈において，最近勃興 してきた計算理論的側面も含めて，講演者自身の共同研究成果と未解決問題も述べる．その際 に，鍵となる概念は，有限束のハッセ図，凸多面体の1骨格，および，有限群のケーリーグラフ である．これらの概念を，まず，コンピュータ・サイエンスにおける基本的な問題であるソー ティングを例として，説明する．そして，カタラン構造，線形計画法，置換群のような離散数学 における概念と組合せ遷移がどのように関係しているのか，紹介する．

  2020.12.25 Fri. 15:00-17:00

  第04回セミナー・勉強会
  話者：岡本 吉央（電気通信大学，C01班） 題目：組合せ遷移と離散構造 概要：