澄田範奈 (Hanna SUMITA)
東京工業大学 情報理工学院 数理・計算科学系
准教授
Department of Mathematical and Computing Science, School of Computing, Tokyo Institute of Technology
Associate Professor
✿ my research group
Publications & Talks /
Research interest /
Teaching (jp) /
Activities /
CV /
Grants (jp)
Publications & Talks
Journal Papers
- Y. Kawase and H. Sumita: Randomized Strategies for Robust Combinatorial Optimization with Approximate Separation.
Algorithmica, accepted.
-
Y. Kawase, K. Kimura, K. Makino, and H. Sumita: Optimal Matroid Partitioning Problems.
Algorithmica, 83, pp. 1653–1676, 2021.
[Paper]
-
Y. Kawase, H. Sumita, and T. Fukunaga: Submodular Maximization with Uncertain Knapsack Capacity.
SIAM Journal on Discrete Mathematics, 33(3), pp. 1121-1145, 2019.
[Paper]
- H. Sumita, N. Kakimura and K. Makino: Total Dual Integrality of the Linear Complementarity Problem.
Annals of Operations Research, 274(1–2), pp. 531–553, 2019.
[Paper]
- H. Sumita, N. Kakimura and K. Makino: Parameterized Complexity of Sparse Linear Complementarity Problems.
Algorithmica, 79(1), pp. 42-65, 2017.
[Paper]
- H. Sumita, N. Kakimura and K. Makino: The Linear Complementarity Problems with a Few Variables per Constraint.
Mathematics of Operations Research, 40(4), pp. 1015-1026, 2015. [Paper]
Refereed Conference Proceedings
- Y. Kawase, H. Sumita and Y. Yokoi: Random Assignment of Indivisible Goods under Constraints.
Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), pp. 2792–2799.
- A. Igarashi, Y. Kawase, W. Suksompong, H. Sumita: Fair Division with Two-Sided Preferences.
Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), pp. 2756–2764.
- Y. Kawase, A. Miyauchi and H. Sumita: Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks.
Proceedings of the 16th ACM International WSDM Conference (WSDM 2023), pp. 886–894.
- Y. Kawase and H. Sumita: Online Max-min Fair Allocation.
Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT 2022), pp. 526–543.
- H. Goko, A. Kawamura, Y. Kawase, K. Makino, and H. Sumita: Online Scheduling on Identical Machines with a Metric State Space.
Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), pp. 32:1–32:21.
- H. Goko, A. Igarashi, Y. Kawase, K. Makino, H. Sumita, A. Tamura, Y. Yokoi, and M. Yokoo: Fair and Truthful Mechanism with Limited Subsidy.
Proceedings of the 21st International Conference on Autonomous Agents and Multi-Agent Systems 2022 (AAMAS 2022), to appear.
- H. Sumita, S. Ito, K. Takemura, D. Hatano, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: Online Task Assignment Problems with Reusable Resources.
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI-22), to appear.
- K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021), pp. 130:3367–3375.
- K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions.
Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI-21), pp. 9791–9798.
- S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: Delay and Cooperation in Nonstochastic Linear Bandits.
Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS 2020), pp. 4872–4883.
- Y. Kawase and H. Sumita: On the Max-min Fair Stochastic Allocation of Indivisible Goods.
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI-20), pp. 2070–2078.
[Paper]
- S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback.
Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS 2019), pp. 10589–10598.
- S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: Improved Regret Bounds for Bandit Combinatorial Optimization.
Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS 2019), pp. 12027–12036.
-
D. Hatano, Y. Kuroki, Y. Kawase, H. Sumita, N. Kakimura, and K. Kawarabayashi: Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising.
Proceedings of the 16th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2019), pp. 568–582 .
- Y. Kawase and H. Sumita: Randomized Strategies for Robust Combinatorial Optimization.
Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI-19), pp. 7876–7883.
(acceptance ratio 1,150/7,095 = 16.2%)
- S. Ito, D. Hatano, H. Sumita, A. Yabe, T. Fukunaga, N. Kakimura, K. Kawarabayashi: Regret Bounds for Online Portfolio Selection with a Cardinality Constraint.
Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS 2018), pp. 10588–10597.
- A. Yabe, D. Hatano, H. Sumita, S. Ito, N. Kakimura, T. Fukunaga, K. Kawarabayashi: Causal Bandits with Propagating Inference.
Proceedings of the 35th International Conference on Machine Learning (ICML 2018), pp. 5512–5520.
[Paper]
- S. Ito, D. Hatano, H. Sumita, A. Yabe, T. Fukunaga, N. Kakimura, K. Kawarabayashi:
Online Regression with Partial Information: Generalization and Linear Projection.
Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018), pp. 1599–1607.
[Paper]
- Y. Kawase, H. Sumita and T. Fukunaga: Submodular maximization with uncertain knapsack capacity.
Proceedings of the 13th Latin American Theoretical Informatics (LATIN 2018), pp. 653–668.
[Paper]
- Y. Kawase, K. Kimura, K. Makino and H. Sumita: Optimal Matroid Partitioning Problems.
Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), pp. 51:1–51:13.
[Paper]
- S. Ito, D. Hatano, H. Sumita, A. Yabe, T. Fukunaga, N. Kakimura and K. Kawarabayashi: Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation.
Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS 2017), pp. 4102–4111.
[Paper]
- H. Sumita, Y. Yonebayashi, N. Kakimura and K. Kawarabayashi: An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization.
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), pp. 4412–4418.
[Paper]
- H. Sumita, Y. Kawase, S. Fujita and T. Fukunaga: Online Optimization of Video-Ad Allocation.
Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), pp. 423–429.
[Paper]
- Y. Kawase, K. Kimura, K. Makino and H. Sumita: Min-sum-max matroid partitioning problem.
Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 335–344.
- T. Maehara, Y. Kawase, H. Sumita, K. Tono and K. Kawarabayashi: Optimal Pricing for Submodular Valuations with Bounded Curvature.
Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), pp. 622–628.
[Paper]
- H. Sumita, N. Kakimura and K. Makino: Parameterized Complexity of Sparse Linear Complementarity Problems.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), pp. 355–364.
- H. Sumita, N. Kakimura and K. Makino: Total Dual Integrality of the Linear Complementarity Problem.
Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 342–351.
- H. Sumita, N. Kakimura and K. Makino: Sparse Linear Complementarity Problems.
Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 453–462.
- H. Sumita, N. Kakimura and K. Makino: Sparse Linear Complementarity Problems.
Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC 2013), pp. 358–369.
Preprints
- Y. Kawase, K. Makino, H. Sumita, A. Tamura, M. Yokoo: Towards Optimal Subsidy Bounds for Envy-freeable Allocations.
arXiv:2308.11230, 2023.
[Page]
- Y. Kawase, K. Nishimura and H. Sumita: Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods.
arXiv:2306.05986, 2023.
[Page]
- K. Nishimura and H. Sumita: Envy-freeness and Maximum Nash Welfare for Mixed Divisible and
Indivisible Goods.
arXiv:2302.13342, 2023.
[Page]
Talks in International Conferences
- A. Igarashi, Y. Kawase, W. Suksompong, H. Sumita: Fair Division with Two-Sided Preferences.
The 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), Macao, August 2023.
- H. Sumita, S. Ito, K. Takemura, D. Hatano, T. Fukunaga, N. Kakimura, and K. Kawarabayashi: Online Task Assignment Problems with Reusable Resources. (Oral and poster)
The 36th AAAI Conference on Artificial Intelligence (AAAI-22), virtual, February 2022.
- Y. Kawase and H. Sumita: Randomized Strategies for Robust Combinatorial Optimization. (highlight and poster)
The 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), Honolulu, USA, January 2019.
- H. Sumita, Y. Yonebayashi, N. Kakimura and K. Kawarabayashi: An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization.
The 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, August 2017.
- Y. Kawase, K. Kimura, K. Makino and H. Sumita: Min-sum-max matroid partitioning problem.
The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 2017.
- H. Sumita, N. Kakimura and K. Makino: Parameterized Complexity of Sparse Linear Complementarity Problems.
The 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Patras, Greece, September 2015.
- H. Sumita, N. Kakimura and K. Makino: Total Dual Integrality of the Linear Complementarity Problem.
The 22nd International Symposium on Mathematical Programming (ISMP 2015), Pittsburgh, USA, July 2015.
- H. Sumita, N. Kakimura and K. Makino: Total Dual Integrality of the Linear Complementarity Problem.
The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, June 2015.
- H. Sumita, N. Kakimura and K. Makino: Sparse Linear Complementarity Problems.
The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Veszprem, Hungary, June 2013.
- H. Sumita, N. Kakimura and K. Makino: Sparse Linear Complementarity Problems.
The 8th International Conference on Algorithms and Complexity (CIAC 2013), Barcelona, Spain, May 2013.
Talks in Domestic Conferences (in Japanese)
- 河瀬康志,澄田範奈: オンライン割当における最小効用最大化,
第21回情報科学技術フォーラム(FIT2022), 慶應義塾大学(ハイブリッド), 2022年9月.
- 河瀬康志,澄田範奈,福永拓郎: 不確実なナップサック制約をもつ劣モジュラ関数最大化,
電子情報通信学会 COMP-ELC学生シンポジウム, 東京電機大学, 2018年3月. 招待講演
- 前原貴憲,河瀬康志,澄田範奈,東野克哉,河原林健一: 劣モジュラ評価関数をもつ最適価格付け問題,
2017年日本オペレーションズ・リサーチ学会春季研究発表会,沖縄県市町村自治会館,2017年3月.
- 澄田範奈,河瀬康志,藤田澄男,福永拓郎: 動画広告割当のオンライン最適化,
日本応用数理学会2016年年会,北九州国際会議場,2016年9月.
- 澄田範奈,河瀬康志,藤田澄男,福永拓郎: 動画広告割当のオンライン最適化,
日本オペレーションズ・リサーチ学会関西支部研究講演会,常翔学園大阪センター,2016年7月.
- 澄田範奈,垣村尚徳,牧野和久: 線形相補性問題のパラメータ化計算量,
2015年日本オペレーションズ・リサーチ学会春季研究発表会,東京理科大学,2015年3月.
- 澄田範奈,垣村尚徳,牧野和久: 線形相補性問題のパラメータ化計算量,
電子情報通信学会 COMP-ELC学生シンポジウム, 立命館大学, 2015年3月. 最優秀論文賞
- 澄田範奈,垣村尚徳,牧野和久: 方向つき線形相補性問題の計算複雑度,
2014年日本オペレーションズ・リサーチ学会秋季研究発表会,北海道科学大学,2014年8月.
- 澄田範奈,垣村尚徳,牧野和久: 線形相補性問題の完全双対整数性,
日本オペレーションズ・リサーチ学会「最適化の理論と応用」研究部会SOTA,筑波大学,2014年6月.
- 澄田範奈,垣村尚徳,牧野和久: 線形相補性問題の整数性,
研究集会「最適化:モデリングとアルゴリズム」, 政策研究大学院大学, 2014年3月.
- 澄田範奈,垣村尚徳,牧野和久: 線形相補性問題の完全双対整数性,
電子情報通信学会 COMP-ELC学生シンポジウム, 新潟大学, 2014年3月.
- 澄田範奈,垣村尚徳,牧野和久: 線形相補性問題の完全双対整数性,
2014年日本オペレーションズ・リサーチ学会春季研究発表会,大阪大学,2014年3月.
- 澄田範奈,垣村尚徳,牧野和久: 疎な線形相補性問題に対する組合せ的アルゴリズム,
電子情報通信学会 COMP学生シンポジウム, 岐阜大学, 2013年3月.
- 澄田範奈,垣村尚徳,牧野和久: 疎な線形相補性問題に対する組合せ的アルゴリズム,
2012年日本オペレーションズ・リサーチ学会秋季研究発表会,ウインクあいち,2012年9月.
- 澄田範奈,垣村尚徳,牧野和久: 疎な線形相補性問題の計算複雑度,
日本オペレーションズ・リサーチ学会「最適化の理論と応用」研究部会SOTA,筑波大学,2012年6-7月.
Talks in Seminars
- Y. Kawase and H. Sumita: Randomized Strategies for Robust Combinatorial Optimization.
NeurIPS Meetup Japan 2020, online, December 9, 2020. Invited talk
- 澄田範奈,河瀬康志,藤田澄男,福永拓郎: Online Optimization of Video-Ad Allocation.
ERATO感謝祭 SeasonIV,学術総合センター,2017年8月4日. (in Japanese)
- H. Sumita, N. Kakimura and K. Makino: The Linear Complementarity Problem: Sparsity and Integrality.
Mittagsseminar, ETH Zurich, March 19, 2015.
Award
Research Interest
- Combinatorial Optimization
- Online Algorithms
- Algorithmic Game Theory
Teaching
2023年度
- 応用線形代数(東京工業大学,学部)2021年度〜(分担)
- 組合せアルゴリズム(東京工業大学,学部)2016年度〜
- 離散最適化(東京工業大学,大学院)2021年度〜
過去に担当した授業
- 2022年度 : 経営科学概論(東京都立大学,学部)
- 2021, 2022年度 : 数理最適化(旧科目名:マネジメント・サイエンスI)(東京都立大学,大学院)
- 2019, 2020年度 : 基礎ゼミナール(首都大学東京 -> 東京都立大学,学部)
- 2019, 2020年度 : 2年次専門セミナー(経営科学)(首都大学東京 -> 東京都立大学,学部)分担
- 2018年度 : 基礎数学2(首都大学東京,学部)
Activities
所属学会
- 日本オペレーションズ・リサーチ学会
- 電子情報通信学会
活動実績
- 日本オペレーションズ・リサーチ学会「離散アルゴリズムの応用と理論」研究部会 幹事(2016〜2018年度) [Page]
- NeurIPS 2019 Top Reviewers
[Page]
- Program Committee of WAOA 2022
- Reviewer of international conferences such as NeurIPS, AAAI, IJCAI, and subreviewers of IPCO, APPROX, COMSOC
CV
Degrees
- March 2010, Bachelor of Engineering from Faculty of Engineering, University of Tokyo
- March 2012, Master of Information Science and Technology from Graduate School of Information Science and Technology, University of Tokyo
- March 2015, Doctor of Information Science and Technology from Graduate School of Information Science and Technology, University of Tokyo
- advisor: Prof. Kazuhisa Makino (moved to Kyoto University in 2013)
Career
- April 2014 - March 2015, Research Fellow of the Japan Society for the Promotion of Science (DC2)
- April 2015 - March 2018, Project researcher, National Institute of Informatics and JST, ERATO, Kawarabayashi Large Graph Project
- April 2018 - March 2020, Assistant Professor, Faculty of Economics and Business Administration, Tokyo Metropolitan University
- April 2020 - March 2023, Associate Professor (Lecturer), Department of Mathematical and Computing Science, School of Computing, Tokyo Institute of Technology
- Since April 2023, Associate Professor, Department of Mathematical and Computing Science, School of Computing, Tokyo Institute of Technology
- Part-time Lecturer (Academic year)
- 2016 - 2019, Tokyo Institute of Technology
- 2020 - 2022, Tokyo Metropolitan University
Grants
- 2021年4月-2026年3月(予定):若手研究「情報の欠如した公平分割問題に対するアルゴリズム」研究代表者
- 2021年4月-2026年3月(予定):基盤研究(B)「不確実性をもつ組合せ最適化モデルに対する理論基盤の構築」研究分担者
- 2017年4月-2021年3月(繰越中):若手研究(B) 「組合せ的制約をもつ線形システムの解法」研究代表者
- 2014年4月-2015年3月:特別研究員DC2「線形相補性問題の整数性に関する研究」