Organization
School of Computing Associate Professor
Title
Associate Professor
External link
SUMITA HANNA
Degree
-
博士（情報理工学） ( 東京大学 )
Research Interests
-
Online Algorithms
-
Combinatorial Optimization
Research Areas
-
Informatics / Mathematical informatics
Education
-
University of Tokyo Graduate School of Information Science and Technology Mathematical Informatics
2012.4 - 2015.3
-
University of Tokyo Graduate School of Information Science and Technology Mathematical Informatics
2010.4 - 2012.3
-
The University of Tokyo Faculty of Engineering
2006.4 - 2010.3
Research History
-
Institute of Science Tokyo
2024.10
-
Tokyo Institute of Technology School of Computing Associate Professor
2023.4 - 2024.9
-
Tokyo Institute of Technology School of Computing Associate Professor (Lecturer)
2020.4 - 2023.3
-
Tokyo Metropolitan University Faculty of Economics and Business Administration Assistant Professor
2018.4 - 2020.3
-
National Institute of Informatics JST, ERATO, Kawarabayashi Large Graph Project Project Researcher
2015.4 - 2018.3
Papers
-
Scheduling on Identical Machines with Setup Time and Unknown Execution Time.
Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, Hanna Sumita
CoRR abs/2507.11311 2025.7
-
Bandit Max-Min Fair Allocation.
Tsubasa Harada, Shinji Ito, Hanna Sumita
CoRR abs/2505.05169 2025.5
-
A general framework for finding diverse solutions via network flow and its applications.
Yuni Iwamasa, Tomoki Matsuda, Shunya Morihira, Hanna Sumita
CoRR abs/2504.17633 2025.4
-
Scheduling on Identical Machines with Setup Time and Unknown Execution Time.
Yasushi Kawase, Kazuhisa Makino, Vinh Long Phan, Hanna Sumita
WADS 41 - 16 2025
-
Towards optimal subsidy bounds for envy-freeable allocations.
Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Makoto Yokoo
Artif. Intell. 348 104406 - 104406 2025
-
Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods.
Koichi Nishimura, Hanna Sumita
Math. Soc. Sci. 138 102449 - 102449 2025
-
A fair and truthful mechanism with limited subsidy
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo
Games and Economic Behavior 144 49 - 70 2024.3
-
Randomized Strategies for Robust Combinatorial Optimization with Approximate Separation.
Yasushi Kawase, Hanna Sumita
Algorithmica 86 ( 2 ) 566 - 584 2024.2
-
Fair division with two-sided preferences.
Ayumi Igarashi 0001, Yasushi Kawase, Warut Suksompong, Hanna Sumita
Games and Economic Behavior 147 268 - 287 2024
-
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets.
Yasushi Kawase, Koichi Nishimura, Hanna Sumita
51st International Colloquium on Automata, Languages, and Programming(ICALP) 96 - 19 2024
-
Towards Optimal Subsidy Bounds for Envy-Freeable Allocations.
Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Makoto Yokoo
AAAI 9824 - 9831 2024
-
New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem.
Koji Ichikawa, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
AAAI 12708 - 12716 2024
-
Bandit Task Assignment with Unknown Processing Time.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
NeurIPS 2023
-
New classes of the greedy-applicable arm feature distributions in the sparse linear bandit problem.
Koji Ichikawa, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
CoRR abs/2312.12400 2023
-
Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods.
Yasushi Kawase, Koichi Nishimura, Hanna Sumita
CoRR abs/2306.05986 2023
-
Fair Division with Two-Sided Preferences.
Ayumi Igarashi 0001, Yasushi Kawase, Warut Suksompong, Hanna Sumita
IJCAI 2756 - 2764 2023
-
Random Assignment of Indivisible Goods under Constraints.
Yasushi Kawase, Hanna Sumita, Yu Yokoi
IJCAI 2792 - 2799 2023
-
Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks.
Yasushi Kawase, Atsushi Miyauchi 0001, Hanna Sumita
WSDM 886 - 894 2023
-
Towards Optimal Subsidy Bounds for Envy-freeable Allocations.
Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Makoto Yokoo
CoRR abs/2308.11230 2023
-
Online Task Assignment Problems with Reusable Resources.
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
CoRR abs/2203.07605 2022
-
Online Task Assignment Problems with Reusable Resources.
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
AAAI 5199 - 5207 2022
-
Fair Division with Two-Sided Preferences.
Ayumi Igarashi 0001, Yasushi Kawase, Warut Suksompong, Hanna Sumita
CoRR abs/2206.05879 2022
-
Fair and Truthful Mechanism with Limited Subsidy.
Hiromichi Goko, Ayumi Igarashi 0001, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo
21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS) 534 - 542 2022
-
Random Assignment of Indivisible Goods under Constraints.
Yasushi Kawase, Hanna Sumita, Yu Yokoi
CoRR abs/2208.07666 2022
-
Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks.
Yasushi Kawase, Atsushi Miyauchi 0001, Hanna Sumita
CoRR abs/2211.03306 2022
-
Online Max-min Fair Allocation.
Yasushi Kawase, Hanna Sumita
SAGT 526 - 543 2022
-
Online Scheduling on Identical Machines with a Metric State Space.
Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita
39th International Symposium on Theoretical Aspects of Computer Science(STACS) 32 - 21 2022
-
Optimal Matroid Partitioning Problems
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita
Algorithmica 83 ( 6 ) 1653 - 1676 2021.6
-
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Thirty-Fifth AAAI Conference on Artificial Intelligence(AAAI) 9791 - 9798 2021
-
A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
The 24th International Conference on Artificial Intelligence and Statistics(AISTATS) 3367 - 3375 2021
-
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
CoRR abs/2101.07957 2021
-
Fair and Truthful Mechanism with Limited Subsidy.
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo
CoRR abs/2105.01801 2021
-
Delay and Cooperation in Nonstochastic Linear Bandits.
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020(NeurIPS) 2020
-
On the Max-Min Fair Stochastic Allocation of Indivisible Goods.
Yasushi Kawase, Hanna Sumita
The Thirty-Fourth AAAI Conference on Artificial Intelligence(AAAI) 2070 - 2078 2020
-
Submodular maximization under uncertain knapsack constraints Reviewed
Yasushui Kawase, Hanna Sumita, Takuro Fukunaga
SIAM Journal on Discrete Mathematics 33 ( 3 ) 1121 - 1145 2019.7
-
Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising. Reviewed
Daisuke Hatano, Yuko Kuroki, Yasushi Kawase, Hanna Sumita, Naonori Kakimura, Ken-ichi Kawarabayashi
PRICAI 2019: Trends in Artificial Intelligence - 16th Pacific Rim International Conference on Artificial Intelligence 568 - 582 2019
-
Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising. Reviewed
Daisuke Hatano, Yuko Kuroki, Yasushi Kawase, Hanna Sumita, Naonori Kakimura, Ken-ichi Kawarabayashi
CoRR abs/1906.05998 2019
-
Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback. Reviewed
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, Canada. 10589 - 10598 2019
-
Total dual integrality of the linear complementarity problem. Reviewed
Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
Annals OR 274 ( 1-2 ) 531 - 553 2019
-
Randomized Strategies for Robust Combinatorial Optimization. Reviewed
Yasushi Kawase, Hanna Sumita
The Thirty-Third AAAI Conference on Artificial Intelligence(AAAI) 7876 - 7883 2019
-
Improved Regret Bounds for Bandit Combinatorial Optimization. Reviewed
Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, Canada. 12027 - 12036 2019
-
Submodular Maximization with Uncertain Knapsack Capacity. Reviewed
Yasushi Kawase, Hanna Sumita, Takuro Fukunaga
SIAM J. Discrete Math. 33 ( 3 ) 1121 - 1145 2019
-
Submodular maximization with uncertain knapsack capacity. Reviewed
Yasushi Kawase, Hanna Sumita, Takuro Fukunaga
CoRR abs/1803.02565 2018
-
Randomized Strategies for Robust Combinatorial Optimization. Reviewed
Yasushi Kawase, Hanna Sumita
CoRR abs/1805.07809 2018
-
Regret Bounds for Online Portfolio Selection with a Cardinality Constraint. Reviewed
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada. 10611 - 10620 2018
-
Causal Bandits with Propagating Inference. Reviewed
Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, Ken-ichi Kawarabayashi
Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018 5508 - 5516 2018
-
Submodular Maximization with Uncertain Knapsack Capacity. Reviewed
Yasushi Kawase, Hanna Sumita, Takuro Fukunaga
LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings 653 - 668 2018
-
Online Regression with Partial Information: Generalization and Linear Projection. Reviewed
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain 1599 - 1607 2018
-
Causal Bandits with Propagating Inference. Reviewed
Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, Ken-ichi Kawarabayashi
CoRR abs/1806.02252 2018
-
Parameterized Complexity of Sparse Linear Complementarity Problems Reviewed
Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
ALGORITHMICA 79 ( 1 ) 42 - 65 2017.9
-
Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation. Reviewed
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA 4102 - 4111 2017
-
Optimal Matroid Partitioning Problems. Reviewed
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita
CoRR abs/1710.00950 2017
-
An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization. Reviewed
Hanna Sumita, Yuma Yonebayashi, Naonori Kakimura, Ken-ichi Kawarabayashi
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 4412 - 4418 2017
-
Optimal Matroid Partitioning Problems. Reviewed
Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita
28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand 51:1-51:13 2017
-
Optimal Pricing for Submodular Valuations with Bounded Curvature. Reviewed
Takanori Maehara, Yasushi Kawase, Hanna Sumita, Katsuya Tono, Ken-ichi Kawarabayashi
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. 622 - 628 2017
-
Online Optimization of Video-Ad Allocation. Reviewed
Hanna Sumita, Yasushi Kawase, Sumio Fujita, Takuro Fukunaga
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017 423 - 429 2017
-
Optimal Pricing for Submodular Valuations with Bounded Curvature. Reviewed
Takanori Maehara, Yasushi Kawase, Hanna Sumita, Katsuya Tono, Ken-ichi Kawarabayashi
CoRR abs/1611.07605 2016
-
The Linear Complementarity Problems with a Few Variables per Constraint Reviewed
Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
MATHEMATICS OF OPERATIONS RESEARCH 40 ( 4 ) 1015 - 1026 2015.11
-
Parameterized Complexity of Sparse Linear Complementarity Problems. Reviewed
Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece 355 - 364 2015
-
Sparse linear complementarity problems Reviewed
Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7878 358 - 369 2013
MISC
-
不確実なナップサック制約をもつ劣モジュラ関数最大化
河瀬康志, 河瀬康志, 澄田範奈, 澄田範奈, 福永拓郎
電子情報通信学会大会講演論文集(CD-ROM) 2018 2018
-
組合せ最適化問題に対する確率的ロバスト最適化
河瀬康志, 澄田範奈
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2018 2018
-
劣モジュラ評価関数をもつ最適価格付け問題
前原貴憲, 前原貴憲, 河瀬康志, 澄田範奈, 東野克哉, 河原林健一
日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2017 2017
-
動画広告割当のオンライン最適化
澄田範奈, 河瀬康志, 藤田澄男, 福永拓郎
日本応用数理学会年会講演予稿集(CD-ROM) 2016 2016
-
1-B-13 線形相補性問題のパラメータ化計算量(学生セッション:離散最適化(3))
澄田 範奈, 垣村 尚徳, 牧野 和久
日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2015 38 - 39 2015.3
-
DS-1-13 Parameterized Complexity of the Linear Complementarity Problem
Sumita Hanna, Kakimura Naonori, Makino Kazuhisa
Proceedings of the IEICE General Conference 2015 ( 1 ) "S - 25"-"S-26" 2015.2
-
1-C-11 方向つき線形相補性問題の計算複雑度(離散最適化(3))
澄田 範奈, 垣村 尚徳, 牧野 和久
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2014 54 - 55 2014.8
-
1-G-10 線形相補性問題の完全双対整数性(離散最適化(2))
澄田 範奈, 垣村 尚徳, 牧野 和久
日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2014 132 - 133 2014.3
-
DS-1-4 On Total Dual Integrality of the Linear Complementarity Problem
Sumita Hanna, Kakimura Naonori, Makino Kazuhisa
Proceedings of the IEICE General Conference 2014 ( 1 ) "S - 7"-"S-8" 2014.3
-
DS-1-8 Combinatorial Algorithms for Sparse Linear Complementarity Problems
Sumita Hanna, Kakimura Naonori, Makino Kazuhisa
Proceedings of the IEICE General Conference 2013 ( 1 ) "S - 15"-"S-16" 2013.3
-
1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))
澄田 範奈, 垣村 尚徳, 牧野 和久
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2012 54 - 55 2012.9
Awards
-
FIT論文賞
2022.12
-
COMP-ELC学生シンポジウム(電子情報通信学会2015年総合大会) 最優秀論文賞
澄田 範奈
Research Projects
-
情報の欠如した公平分割問題に対するアルゴリズム
Grant number：21K17708 2021.4 - 2026.3
日本学術振興会 科学研究費助成事業 若手研究
澄田 範奈
Grant amount：\4290000 （ Direct Cost: \3300000 、 Indirect Cost：\990000 ）
本研究の目的は，不可分財を複数人で公平に分けるという公平分割問題において，財に対する効用（うれしさ）の情報が厳密には分からない状況にも対応できるアルゴリズム理論を構築することである．公平分割問題は，資源や仕事の配分といった場面で現れる実用上も重要な問題である．実用上は財や効用の情報が厳密には分からないことも多々あるため，本研究では情報が欠如した状況に対応するための理論を整備する．
2021年度は主に，例えばフードバンクにおける食料の配分のように，財が逐次的に与えられる状況での公平分割問題に取り組んだ．このような状況は，組合せ最適化におけるオンライン最適化の枠組みで捉えることができる．オンライン最適化では財の与えられ方のモデルがいくつかあり，本研究では(1)与えられる財が敵対的に選ばれる設定と(2)与えられる財が未知の確率分布に従う設定を扱った．また，公平性の指標はいくつかあり，本研究では人々の中で最小の効用が最大になるようにするという意味での公平性に着目した．この意味でのオンライン公平分割問題に対するアルゴリズムを構築し，どれくらいの公平性を達成できるかを理論的に解析した．ここで，アルゴリズムの結果の良さは，「情報を事前に知っていれば達成できたはずの状況」との比較で行った（競合比解析）．本研究はこの意味で理論的に最適なオンラインアルゴリズムを与えた．この成果は論文にまとめてプレプリントとして公開済みである．
他にも，研究課題に関連して，補助金を用いた公平割当問題やオンラインタスク割当の研究も行い，国際会議で発表した． -
Theory and algorithms for combinatorial optimization under uncertainty
Grant number：21H03397 2021.4 - 2026.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
Grant amount：\17160000 （ Direct Cost: \13200000 、 Indirect Cost：\3960000 ）
-
Theory and algorithms for combinatorial optimization under uncertainty
Grant number：23K21646 2021.4 - 2026.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
Grant amount：\17160000 （ Direct Cost: \13200000 、 Indirect Cost：\3960000 ）
-
組合せ的制約をもつ線形システムの解法
Grant number：17K12646 2017.4 - 2023.3
日本学術振興会 科学研究費助成事業 若手研究(B)
澄田 範奈
Grant amount：\3770000 （ Direct Cost: \2900000 、 Indirect Cost：\870000 ）
本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような現実的な状況を動機としたオンラインマッチングの研究が盛んに行われている．現実には，(1) 労働者が割り当てられた仕事を終えたら次の仕事を受け入れ可能であり，(2) 労働者が割り当てられた仕事を確率的に断ることがあり，さらに(3) ひとつのタスクを複数の労働者に割り当てられることがある．本研究はこれらの設定を考慮したオンラインタスク割当問題のアルゴリズムを提案した．アルゴリズムの結果の良さは「情報を事前に知っていれば達成可能な最大利益」との比較で評価することが一般的である（競合比解析）．本研究は提案アルゴリズムがある条件下では理論的に最適であることを示した．さらに，提案アルゴリズムは関連研究の設定にも適用可能であり，既存アルゴリズムよりも良い性能をもつことも示した．この成果は国際会議AAAI-22で発表済みである．
他にも，これまでも着目してきたマトロイド制約に関係する公平割当問題の研究も行い，その成果は国際会議で発表済みである． -
線形相補性問題の整数性に関する研究
Grant number：14J10346 2014.4 - 2016.3
日本学術振興会 科学研究費助成事業 特別研究員奨励費
澄田 範奈
Grant amount：\1700000 （ Direct Cost: \1700000 ）
数理計画法の分野では，制約，条件を満たす解を求める手法が研究されている．本研究では，数理計画法において基礎的かつ理論的にも実用上も重要な，線形相補性問題と呼ばれる問題を扱う．この問題は，行列とベクトルが与えられたとき，条件を満たすベクトルを求める問題である．線形相補性問題は，線形計画問題や凸二次計画問題，双行列ゲームといった基本的な問題を含み，経済学や力学といった周辺分野にも応用をもつ．
<br>
本研究では，線形相補性問題の解ベクトルの中でも特に，整数ベクトルの解（整数解）が存在するための十分条件に着目した．応用によっては，整数解を得ることが必要な状況があるためである．線形相補性問題の整数解に関する先行研究では，入力行列が主単模と呼ばれる性質をもつならば，基底解が整数となることを示している．一方，線形相補性問題の特殊ケースである線形計画問題（線形制約を満たす中で線形関数を最大にするベクトルを求める問題）では，入力行列の完全単模性や，その拡張である線形制約の完全双対整数性が，整数最適解の存在を保証する性質として知られている．また，主単模行列は完全単模行列のひとつの拡張であり，先行研究で線形計画問題の結果の拡張に対応する結果が知られている．
<br>
本研究の成果は，線形相補性問題の完全双対整数性を提案し，線形計画問題で知られている結果に対応する線形相補性問題の結果を得たことである．本研究のような研究がなされていなかったのは，線形相補性問題の「双対性」に関する研究が少なかったことがひとつの理由である．本研究では，新たに「方向つき線形相補性問題」を導入し，これを用いて線形相補性問題の双対性を提案した．本研究の成果は現在論文誌に投稿中であり，国内学会で発表を行った．
Teaching Experience
-
経営科学概論
2022 Institution：東京都立大学
-
応用線形代数
2021 Institution：東京工業大学
-
基礎ゼミナール
2019 - 2020 Institution：首都大学東京
-
基礎数学2
2018 Institution：首都大学東京
-
組合せアルゴリズム
2016 Institution：東京工業大学