HOME
代表挨拶
2023年3月
2021年3月
2023年3月
2021年3月
プロジェクト
研究プロジェクト概要
A01班
B01班
C01班
活動情報
トピックス
イベントの記録
ニュースレター
主な成果
最終報告書
論文・受賞
産学連携研究
研究用コンテンツ
JP/
EN
HOME
代表挨拶
2023年3月
2021年3月
2023年3月
2021年3月
プロジェクト
研究プロジェクト概要
A01班
B01班
C01班
活動情報
トピックス
イベントの記録
ニュースレター
主な成果
最終報告書
論文・受賞
産学連携研究
研究用コンテンツ
JP/
EN
活動情報
イベントの記録
2020年度
2021年度
2022年度
2023年度
A01
B01
C01
セミナー
公開イベント
領域内部イベント
グラフの向き付けとは,無向グラフの各辺に向きを付けて有向グラフを得ることをいい,組合せ最適化やグラフ理論の分野で盛んに研究されているトピックである.本講演では,連結度制約を保ちながら向き付けの辺の向きを1本ずつ変更していく,「グラフ向き付けの遷移」に関する講演者らの最新の成果について紹介する.我々の主結果は,「2k辺連結無向グラフの任意の向き付けに対して,うまく辺の向きを1本ずつ変更していくことで辺連結度を単調に増加させ,最終的にk辺連結向き付けを得ることができる」というものである.これは,古典的な Nash-Williams の定理を強めた結果であり,k辺連結向き付けのフリップ・グラフの連結性を議論する際にも有用である.
なお,この成果は本プロジェクトメンバーとの共同研究に基づくものであり,SODA2022で発表予定である.
2021.11.11 Thu. 10:00-12:00
第17回セミナー・勉強会
話者:
小林 佑輔(京都大学,C01班)
題目:
連結度制約付きグラフ向き付けの遷移
概要:
グラフの向き付けとは,無向グラフの各辺に向きを付けて有向グラフを得ることをいい,組合せ最適化やグラフ理論の分野で盛んに研究されているトピックである.本講演では,連結度制約を保ちながら向き付けの辺の向きを1本ずつ変更していく,「グラフ向き付けの遷移」に関する講演者らの最新の成果について紹介する.我々の主結果は,「2k辺連結無向グラフの任意の向き付けに対して,うまく辺の向きを1本ずつ変更していくことで辺連結度を単調に増加させ,最終的にk辺連結向き付けを得ることができる」というものである.これは,古典的な Nash-Williams の定理を強めた結果であり,k辺連結向き付けのフリップ・グラフの連結性を議論する際にも有用である. なお,この成果は本プロジェクトメンバーとの共同研究に基づくものであり,SODA2022で発表予定である.
セミナー
2021年度
C01
トークンスライディング問題(TS問題)は組合せ遷移において最もよく研究されている問題のひとつである.本講演ではこの問題の有向グラフ版である有向トークンスライディング問題(有向TS問題)を考える.TS問題ではトークンを辺の向きに沿ってどちら向きにも動かせるが,有向TS問題ではトークンを辺の向きに沿ってしか動かせないという非対称性がある.無向辺は逆向きの2つの有向辺で模倣できるため,有向TS問題はTS問題の一般化である.本講演では,有向TS問題に対して,グラフクラスを限定した場合の困難性を示す.また,主結果として,入力が木を向き付けたグラフの場合に多項式時間で解けることを示す.本講演の内容はA01班,C01班のメンバーと大学院生を含む共同研究に基づく.
2021.10.21 Thu. 10:00-12:00
第16回セミナー・勉強会
話者:
中畑 裕(奈良先端科学技術大学院大学)
題目:
有向グラフ上のトークンスライディング問題
概要:
トークンスライディング問題(TS問題)は組合せ遷移において最もよく研究されている問題のひとつである.本講演ではこの問題の有向グラフ版である有向トークンスライディング問題(有向TS問題)を考える.TS問題ではトークンを辺の向きに沿ってどちら向きにも動かせるが,有向TS問題ではトークンを辺の向きに沿ってしか動かせないという非対称性がある.無向辺は逆向きの2つの有向辺で模倣できるため,有向TS問題はTS問題の一般化である.本講演では,有向TS問題に対して,グラフクラスを限定した場合の困難性を示す.また,主結果として,入力が木を向き付けたグラフの場合に多項式時間で解けることを示す.本講演の内容はA01班,C01班のメンバーと大学院生を含む共同研究に基づく.
セミナー
2021年度
講演者は,グラフ最適化問題についての計算複雑性について研究を行っている.グラフ最適化問題の中で,特徴Pをもつ最大誘導部分グラフ探索問題 (Maximum Induced Subgraph with Property P) がある.例えば,特徴が独立集合であるとき,この問題は最大独立頂点集合問題としてみることができる.グラフGが特徴Pを持ち,グラフGにおいてどの誘導部分グラフも特徴Pを持つとき,その特徴Pは遺伝性があるという.この最大誘導部分グラフ探索問題は,特徴Pが遺伝性を持つとき,一般グラフにおいて近似困難であることが知られている.本講演では,遺伝性を持たない正則性などを特徴とした最大誘導部分グラフ探索問題に対して,入力グラフの構造を制限したときの計算複雑性について紹介する.
2021.10.07 Thu. 10:00-12:00
第15回セミナー・勉強会
話者:
江藤 宏(東北大学,A01班)
題目:
最大誘導部分グラフ探索問題の計算困難性について
概要:
講演者は,グラフ最適化問題についての計算複雑性について研究を行っている.グラフ最適化問題の中で,特徴Pをもつ最大誘導部分グラフ探索問題 (Maximum Induced Subgraph with Property P) がある.例えば,特徴が独立集合であるとき,この問題は最大独立頂点集合問題としてみることができる.グラフGが特徴Pを持ち,グラフGにおいてどの誘導部分グラフも特徴Pを持つとき,その特徴Pは遺伝性があるという.この最大誘導部分グラフ探索問題は,特徴Pが遺伝性を持つとき,一般グラフにおいて近似困難であることが知られている.本講演では,遺伝性を持たない正則性などを特徴とした最大誘導部分グラフ探索問題に対して,入力グラフの構造を制限したときの計算複雑性について紹介する.
セミナー
2021年度
A01
伊藤健洋 (領域代表,東北大学) が,日本オペレーションズ・リサーチ学会「最適化手法とアルゴリズム」 研究部会(SOMA)にて講演します.
講演1:黒木 祐子 氏(東京大学)「限られた観測に基づく組合せ最適腕識別問題」
講演2:伊藤 健洋(東北大学)「組合せ遷移への招待」
参加お申込みは,研究部会のWebサイトをご覧ください.
「最適化手法とアルゴリズム」 研究部会(SOMA)へのリンク
2021.09.27 Mon. 14:00-18:00
日本オペレーションズ・リサーチ学会「最適化手法とアルゴリズム」 研究部会にて講演
話者:
題目:
概要:
伊藤健洋 (領域代表,東北大学) が,日本オペレーションズ・リサーチ学会「最適化手法とアルゴリズム」 研究部会(SOMA)にて講演します. 講演1:黒木 祐子 氏(東京大学)「限られた観測に基づく組合せ最適腕識別問題」 講演2:伊藤 健洋(東北大学)「組合せ遷移への招待」 参加お申込みは,研究部会のWebサイトをご覧ください. 「最適化手法とアルゴリズム」 研究部会(SOMA)へのリンク
公開イベント
2021年度
2021年9月1日(水)
14:00-15:15
【招待講演】池上 敦子 先生(成蹊大学)
「ナーススケジューリングにおける解の多様性と類似性」
15:30-16:30
本研究領域の活動報告・今後の予定
(18:00-)
(オンライン懇親会)
【池上敦子先生 ご講演概要】
ナーススケジューリングでは,各ナースの健康状態や社会生活を守るための制約を満たしながら,各日の各シフトに適切なスキルレベルのナースを適切な人数配置する必要がある.また,勤務表作成者が持つ「暗黙的な制約や評価尺度」を無視できないため,実用できる解を得るためには,最適解を1つ得るといった単純な最適化方法では不十分だと考えられる.効率の良い解修正のためには,解空間をなんらかの形で把握できる情報が重要である.与えられた解に対し,わずかに修正された解が望まれる場合と,まったく異なる解が望まれる場合があることから,複数の最適解を対象に,多様性と類似性を考慮する必要がある.
本講演では,最適解列挙からわかったことや,制約式における意思決定変数の登場頻度と解の多様性の関係について考えたこと,を紹介する.
2021.09.01 Wed. 14:00-16:30
公開シンポジウム
話者:
題目:
概要:
2021年9月1日(水) 14:00-15:15 【招待講演】池上 敦子 先生(成蹊大学) 「ナーススケジューリングにおける解の多様性と類似性」 15:30-16:30 本研究領域の活動報告・今後の予定 (18:00-) (オンライン懇親会) 【池上敦子先生 ご講演概要】 ナーススケジューリングでは,各ナースの健康状態や社会生活を守るための制約を満たしながら,各日の各シフトに適切なスキルレベルのナースを適切な人数配置する必要がある.また,勤務表作成者が持つ「暗黙的な制約や評価尺度」を無視できないため,実用できる解を得るためには,最適解を1つ得るといった単純な最適化方法では不十分だと考えられる.効率の良い解修正のためには,解空間をなんらかの形で把握できる情報が重要である.与えられた解に対し,わずかに修正された解が望まれる場合と,まったく異なる解が望まれる場合があることから,複数の最適解を対象に,多様性と類似性を考慮する必要がある. 本講演では,最適解列挙からわかったことや,制約式における意思決定変数の登場頻度と解の多様性の関係について考えたこと,を紹介する.
公開イベント
2021年度
2021.09.01 Wed. 10:00-13:40
第3回領域会議
話者:
題目:
概要:
領域内部イベント
2021年度
2021.08.30 Mon.
Workshop "Combinatorial Reconfiguration in Discrete and Computational Geometry"
話者:
題目:
概要:
公開イベント
2021年度
JCCA-2021・ 離散数学とその応用研究集会2021
にて,組合せ遷移のミニシンポジウムを企画・開催します.
伊藤 健洋 (東北大学)「組合せ遷移への招待」
中畑 裕 (京都大学)「Reconfiguring Directed Trees in a Digraph」
岡本 吉央 (電気通信大学)「単位円配置の遷移 ― 連続的な組合せ遷移」
鮏川 矩義 (東京理科大学)「整凸多面体の組合せ的直径とその周辺」
* 本ミニシンポジウムでは,全てオンライン発表の予定です.
2021.08.19 Thur. 10:35-12:50
JCCA-2021 ミニシンポジウム
話者:
題目:
概要:
JCCA-2021・ 離散数学とその応用研究集会2021にて,組合せ遷移のミニシンポジウムを企画・開催します. 伊藤 健洋 (東北大学)「組合せ遷移への招待」 中畑 裕 (京都大学)「Reconfiguring Directed Trees in a Digraph」 岡本 吉央 (電気通信大学)「単位円配置の遷移 ― 連続的な組合せ遷移」 鮏川 矩義 (東京理科大学)「整凸多面体の組合せ的直径とその周辺」 * 本ミニシンポジウムでは,全てオンライン発表の予定です.
公開イベント
2021年度
講演者はトポロジー(位相幾何学)を専門とし,図形や空間の性質を研究している.トポロジーに由来する発想や道具は数学全体に波及し,最近では数学以外でも「トポロジカル」という形容詞を目にする機会が増えた.トポロジーのおもしろさの1つは,幾何的な入力から群などの代数的な出力を得る過程にある.本講演では具体的な問題を題材として,その考え方や捉え方をお伝えしたい.また講演者が組合せ遷移のプロジェクトに参加して興味を持った話題にも言及する予定である.
2021.07.26 Mon. 10:00-12:00
第14回セミナー・勉強会
話者:
野崎 雄太(広島大学,C01班)
題目:
トポロジーの視点
概要:
講演者はトポロジー(位相幾何学)を専門とし,図形や空間の性質を研究している.トポロジーに由来する発想や道具は数学全体に波及し,最近では数学以外でも「トポロジカル」という形容詞を目にする機会が増えた.トポロジーのおもしろさの1つは,幾何的な入力から群などの代数的な出力を得る過程にある.本講演では具体的な問題を題材として,その考え方や捉え方をお伝えしたい.また講演者が組合せ遷移のプロジェクトに参加して興味を持った話題にも言及する予定である.
セミナー
2021年度
C01
国際会議The 48th International Colloquium on Automata, Languages, and Programming (
ICALP 2021
) にて,組合せ遷移に関するサテライトワークショップを企画・開催します.
詳細は,
英語版のイベント情報
をご覧ください.
2021.07.12 Mon.
Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2021
話者:
題目:
概要:
国際会議The 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) にて,組合せ遷移に関するサテライトワークショップを企画・開催します. 詳細は,英語版のイベント情報をご覧ください.
公開イベント
2021年度
1
…
1
2
3
4
5
6
7
…
7
活動情報
トピックス
イベントの記録
ニュースレター
no cache