2025/10/02 更新

写真a

スミタ　ハンナ
澄田　範奈
SUMITA HANNA
所属
情報理工学院 准教授
職名
准教授
外部リンク

学位

  • 博士（情報理工学） （ 東京大学 ）

研究キーワード

  • オンラインアルゴリズム

  • 組合せ最適化

研究分野

  • 情報通信 / 数理情報学

学歴

  • 東京大学大学院   情報理工学系研究科   数理情報学専攻 博士課程

    2012年4月 - 2015年3月

    　 詳細を見る

  • 東京大学大学院   情報理工学系研究科   数理情報学専攻 修士課程

    2010年4月 - 2012年3月

    　 詳細を見る

  • 東京大学   工学部   計数工学科

    2006年4月 - 2010年3月

    　 詳細を見る

経歴

  • 東京科学大学

    2024年10月 - 現在

    　 詳細を見る

  • 東京工業大学   情報理工学院   准教授

    2023年4月 - 2024年9月

    　 詳細を見る

  • 東京工業大学   情報理工学院   講師

    2020年4月 - 2023年3月

    　 詳細を見る

  • 首都大学東京   経済経営学部   助教

    2018年4月 - 2020年3月

    　 詳細を見る

  • 国立情報学研究所   ビッグデータ数理国際研究センター   特任研究員

    2015年4月 - 2018年3月

    　 詳細を見る

論文

▼全件表示

MISC

  • 不確実なナップサック制約をもつ劣モジュラ関数最大化

    河瀬康志, 河瀬康志, 澄田範奈, 澄田範奈, 福永拓郎

    電子情報通信学会大会講演論文集(CD-ROM)   2018   2018年

    　詳細を見る

  • 組合せ最適化問題に対する確率的ロバスト最適化

    河瀬康志, 澄田範奈

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2018   2018年

    　詳細を見る

  • 劣モジュラ評価関数をもつ最適価格付け問題

    前原貴憲, 前原貴憲, 河瀬康志, 澄田範奈, 東野克哉, 河原林健一

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集   2017   2017年

    　詳細を見る

  • 動画広告割当のオンライン最適化

    澄田範奈, 河瀬康志, 藤田澄男, 福永拓郎

    日本応用数理学会年会講演予稿集(CD-ROM)   2016   2016年

    　詳細を見る

  • 1-B-13 線形相補性問題のパラメータ化計算量(学生セッション:離散最適化(3))

    澄田 範奈, 垣村 尚徳, 牧野 和久

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集   2015   38 - 39   2015年3月

    　詳細を見る

    記述言語：日本語   出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    researchmap

  • DS-1-13 線形相補性問題のパラメータ化計算量(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

    澄田 範奈, 垣村 尚徳, 牧野 和久

    電子情報通信学会総合大会講演論文集   2015 ( 1 )   "S - 25"-"S-26"   2015年2月

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

    CiNii Books

    researchmap

  • 1-C-11 方向つき線形相補性問題の計算複雑度(離散最適化(3))

    澄田 範奈, 垣村 尚徳, 牧野 和久

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2014   54 - 55   2014年8月

    　詳細を見る

    記述言語：日本語   出版者・発行元：社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    researchmap

  • 1-G-10 線形相補性問題の完全双対整数性(離散最適化(2))

    澄田 範奈, 垣村 尚徳, 牧野 和久

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集   2014   132 - 133   2014年3月

    　詳細を見る

    記述言語：日本語   出版者・発行元：社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    researchmap

  • DS-1-4 線形相補性問題の完全双対整数性(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

    澄田 範奈, 垣村 尚徳, 牧野 和久

    電子情報通信学会総合大会講演論文集   2014 ( 1 )   "S - 7"-"S-8"   2014年3月

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

    CiNii Books

    researchmap

  • DS-1-8 疎な線形相補性問題に対する組合せ的アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)

    澄田 範奈, 垣村 尚徳, 牧野 和久

    電子情報通信学会総合大会講演論文集   2013 ( 1 )   "S - 15"-"S-16"   2013年3月

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人電子情報通信学会  

    CiNii Books

    researchmap

  • 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))

    澄田 範奈, 垣村 尚徳, 牧野 和久

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   2012   54 - 55   2012年9月

    　詳細を見る

    記述言語：日本語   出版者・発行元：社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    researchmap

▼全件表示

受賞

  • FIT論文賞

    2022年12月  

    　詳細を見る

  • COMP-ELC学生シンポジウム(電子情報通信学会2015年総合大会) 最優秀論文賞

    澄田 範奈

    　詳細を見る

共同研究・競争的資金等の研究課題

  • 情報の欠如した公平分割問題に対するアルゴリズム

    研究課題/領域番号：21K17708  2021年4月 - 2026年3月

    日本学術振興会  科学研究費助成事業  若手研究

    澄田 範奈

    　 詳細を見る

    配分額：4290000円 （ 直接経費：3300000円 、 間接経費：990000円 ）

    本研究の目的は，不可分財を複数人で公平に分けるという公平分割問題において，財に対する効用（うれしさ）の情報が厳密には分からない状況にも対応できるアルゴリズム理論を構築することである．公平分割問題は，資源や仕事の配分といった場面で現れる実用上も重要な問題である．実用上は財や効用の情報が厳密には分からないことも多々あるため，本研究では情報が欠如した状況に対応するための理論を整備する．
    2021年度は主に，例えばフードバンクにおける食料の配分のように，財が逐次的に与えられる状況での公平分割問題に取り組んだ．このような状況は，組合せ最適化におけるオンライン最適化の枠組みで捉えることができる．オンライン最適化では財の与えられ方のモデルがいくつかあり，本研究では(1)与えられる財が敵対的に選ばれる設定と(2)与えられる財が未知の確率分布に従う設定を扱った．また，公平性の指標はいくつかあり，本研究では人々の中で最小の効用が最大になるようにするという意味での公平性に着目した．この意味でのオンライン公平分割問題に対するアルゴリズムを構築し，どれくらいの公平性を達成できるかを理論的に解析した．ここで，アルゴリズムの結果の良さは，「情報を事前に知っていれば達成できたはずの状況」との比較で行った（競合比解析）．本研究はこの意味で理論的に最適なオンラインアルゴリズムを与えた．この成果は論文にまとめてプレプリントとして公開済みである．
    他にも，研究課題に関連して，補助金を用いた公平割当問題やオンラインタスク割当の研究も行い，国際会議で発表した．

    researchmap

  • 不確実性をもつ組合せ最適化モデルに対する理論基盤の構築

    研究課題/領域番号：21H03397  2021年4月 - 2026年3月

    日本学術振興会  科学研究費助成事業  基盤研究(B)

    垣村 尚徳, 田村 明久, 福永 拓郎, 澄田 範奈

    　 詳細を見る

    配分額：17160000円 （ 直接経費：13200000円 、 間接経費：3960000円 ）

    researchmap

  • 不確実性をもつ組合せ最適化モデルに対する理論基盤の構築

    研究課題/領域番号：23K21646  2021年4月 - 2026年3月

    日本学術振興会  科学研究費助成事業  基盤研究(B)

    垣村 尚徳, 田村 明久, 澄田 範奈, 福永 拓郎

    　 詳細を見る

    配分額：17160000円 （ 直接経費：13200000円 、 間接経費：3960000円 ）

    本研究課題では，不確実性をもつ組合せ最適化モデルに対して，計算効率性や近似可能性を特徴付ける組合せ構造の解析を行なうことを目指す．期間2年目である今年度は，昨年度に引き続いて，関連する文献や国際会議における研究動向の調査，および，海外の共同研究者との情報交換を行なった．そして，基本的な組合せ最適化問題であるマッチング問題を中心に，入力データの不確実性が計算効率性に与える影響を解析した．特に，オンラインマッチング問題やその一般化であるオンラインタスク割り当て問題に対して，再利用可能である場合や遅延を許す場合などの実用的な状況を動機とした問題設定を考えて，理論保証をもつアルゴリズムを設計した．遅延を許す場合のオンラインマッチング問題に関する成果は，査読付き国際会議The 29th International Computing and Combinatorics Conference (COCOON 2023)に採択されて，Best Paper Awardsを受賞した．また，昨年度の成果（AAAI-22, WINE2021）を合わせて，日本オペレーションズリサーチ学会第 35 回 RAMP 数理最適化シンポジウム (RAMP 2023)において招待講演を行った．そのほかにも，オンラインタスク割り当て問題を動機として，処理時間を考慮した確率的バンディット問題を提案して，理論保証をもつアルゴリズムを与えた．この成果は，機械学習分野の査読付き国際会議である Advances in Neural Information Processing Systems 36 (NeurIPS 2023) に採択された．

    researchmap

  • 組合せ的制約をもつ線形システムの解法

    研究課題/領域番号：17K12646  2017年4月 - 2023年3月

    日本学術振興会  科学研究費助成事業  若手研究(B)

    澄田 範奈

    　 詳細を見る

    配分額：3770000円 （ 直接経費：2900000円 、 間接経費：870000円 ）

    本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような現実的な状況を動機としたオンラインマッチングの研究が盛んに行われている．現実には，(1) 労働者が割り当てられた仕事を終えたら次の仕事を受け入れ可能であり，(2) 労働者が割り当てられた仕事を確率的に断ることがあり，さらに(3) ひとつのタスクを複数の労働者に割り当てられることがある．本研究はこれらの設定を考慮したオンラインタスク割当問題のアルゴリズムを提案した．アルゴリズムの結果の良さは「情報を事前に知っていれば達成可能な最大利益」との比較で評価することが一般的である（競合比解析）．本研究は提案アルゴリズムがある条件下では理論的に最適であることを示した．さらに，提案アルゴリズムは関連研究の設定にも適用可能であり，既存アルゴリズムよりも良い性能をもつことも示した．この成果は国際会議AAAI-22で発表済みである．
    他にも，これまでも着目してきたマトロイド制約に関係する公平割当問題の研究も行い，その成果は国際会議で発表済みである．

    researchmap

  • 線形相補性問題の整数性に関する研究

    研究課題/領域番号：14J10346  2014年4月 - 2016年3月

    日本学術振興会  科学研究費助成事業  特別研究員奨励費

    澄田 範奈

    　 詳細を見る

    配分額：1700000円 （ 直接経費：1700000円 ）

    数理計画法の分野では，制約，条件を満たす解を求める手法が研究されている．本研究では，数理計画法において基礎的かつ理論的にも実用上も重要な，線形相補性問題と呼ばれる問題を扱う．この問題は，行列とベクトルが与えられたとき，条件を満たすベクトルを求める問題である．線形相補性問題は，線形計画問題や凸二次計画問題，双行列ゲームといった基本的な問題を含み，経済学や力学といった周辺分野にも応用をもつ．
    <br>
    本研究では，線形相補性問題の解ベクトルの中でも特に，整数ベクトルの解（整数解）が存在するための十分条件に着目した．応用によっては，整数解を得ることが必要な状況があるためである．線形相補性問題の整数解に関する先行研究では，入力行列が主単模と呼ばれる性質をもつならば，基底解が整数となることを示している．一方，線形相補性問題の特殊ケースである線形計画問題（線形制約を満たす中で線形関数を最大にするベクトルを求める問題）では，入力行列の完全単模性や，その拡張である線形制約の完全双対整数性が，整数最適解の存在を保証する性質として知られている．また，主単模行列は完全単模行列のひとつの拡張であり，先行研究で線形計画問題の結果の拡張に対応する結果が知られている．
    <br>
    本研究の成果は，線形相補性問題の完全双対整数性を提案し，線形計画問題で知られている結果に対応する線形相補性問題の結果を得たことである．本研究のような研究がなされていなかったのは，線形相補性問題の「双対性」に関する研究が少なかったことがひとつの理由である．本研究では，新たに「方向つき線形相補性問題」を導入し，これを用いて線形相補性問題の双対性を提案した．本研究の成果は現在論文誌に投稿中であり，国内学会で発表を行った．

    researchmap

担当経験のある科目（授業）

  • 経営科学概論

    2022年 機関名：東京都立大学

    　詳細を見る

  • 応用線形代数

    2021年 - 現在 機関名：東京工業大学

    　詳細を見る

  • 基礎ゼミナール

    2019年 - 2020年 機関名：首都大学東京

    　詳細を見る

  • 基礎数学2

    2018年 機関名：首都大学東京

    　詳細を見る

  • 組合せアルゴリズム

    2016年 - 現在 機関名：東京工業大学

    　詳細を見る