Information and Communication Sciences

宮本 裕一郎

ミヤモト ユウイチロウ  (Miyamoto Yuichiro)

基本情報

所属
上智大学 理工学部情報理工学科 准教授
学位
修士(工学)(東京大学)
博士(情報理工学)(東京大学)

研究者番号
20323850
J-GLOBAL ID
200901028424108863
researchmap会員ID
5000008983

外部リンク

私は主に組合せ最適化問題を研究しています.産業で生じる問題を組合せ最適化問題としてモデル化する方法,モデル化した問題を効率的に解くためのアルゴリズムの開発,さらには計算機科学におけるアルゴリズムの基礎などを研究しています.


経歴

 5

学歴

 1

論文

 50
  • 根本 俊男, 宮本 裕一郎
    選挙研究 39(2) 171-189 2024年3月  査読有り
  • Ken-ichi TANAKA, Ryuhei MIYASHIRO, Yuichiro MIYAMOTO
    Journal of Advanced Mechanical Design, Systems, and Manufacturing 12(3) JAMDSM0065-JAMDSM0065 2018年7月20日  査読有り
  • Tomomi Matsui, Yuichiro Miyamoto
    Journal of the Operations Research Society of Japan 61(1) 151-162 2018年1月1日  査読有り
    This paper discusses the problem of determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exist theorems which characterize Delaunay graphs and yield polynomial time algorithms for the problem only by solving some linear inequality systems. A polynomial time algorithm proposed by Hodgson, Rivin and Smith solves a linear inequality system given by Rivin, which is based on sophisticated arguments about hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another linear inequality system and a polynomial time algorithm. Although their discussion is based on primitive arguments on Euclidean geometry, their proofs are long and intricate, unfortunately. In this paper, we give a simple proof of the theorem shown by Hiroshima et al. by employing the fixed point theorem.
  • Atsushi Miyauchi, Yuichiro Miyamoto
    EUROPEAN PHYSICAL JOURNAL B 86(7) 2013年7月  査読有り
    Modularity proposed by Newman and Girvan is a quality function for community detection. Numerous heuristics for modularity maximization have been proposed because the problem is NP-hard. However, the accuracy of these heuristics has yet to be properly evaluated because computational experiments typically use large networks whose optimal modularity is unknown. In this study, we propose two powerful methods for computing a nontrivial upper bound of modularity. More precisely, our methods can obtain the optimal value of a linear programming relaxation of the standard integer linear programming for modularity maximization. The first method modifies the traditional row generation approach proposed by Grotschel and Wakabayashi to shorten the computation time. The second method is based on a row and column generation. In this method, we first solve a significantly small subproblem of the linear programming and iteratively add rows and columns. Owing to the speed and memory efficiency of these proposed methods, they are suitable for large networks. In particular, the second method consumes exceedingly small memory capacity, enabling us to compute the optimal value of the linear programming for the Power Grid network (consisting of 4941 vertices and 6594 edges) on a standard desktop computer.

MISC

 11
  • 渡邉一生, 宮本裕一郎
    日本オペレーションズ・リサーチ学会2018年春期研究発表会アブストラクト集 1-A-6-1-A-6 2018年3月15日  
  • 宮本裕一郎
    オペレーションズ・リサーチ 60(12) 706-713 2015年12月1日  査読有り招待有り
    この記事は,オペレーションズ・リサーチの中でも特に組合せ最適化,あるいは離散アルゴリズムでよく用いられるグラフ理論の記法の手ほどきを目的としている.グラフ理論の記法では,集合や関数の使い方が重要である.よって,まず集合や関数についても少しだけ紹介した後に,グラフ理論の初歩を紹介する.そして,グラフ理論の記法の使い方の例として美術館定理を扱う.高校数学程度の論理的議論はできるがグラフ理論の数理的記述には慣れていないという読者を想定している.
  • Tomomi Matsui, Yuichiro Miyamoto
    Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012 241-246 2012年12月1日  
    This paper discusses a problem for determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangula- Tion. There exists a theorem which characterizes De- launay graphs and yields a polynomial time algorithm for the problem only by solving a certain linear inequal- ity system. The theorem was proved by Rivin based on arguments of hyperbolic geometry. Independently, Hi- roshima, Miyamoto and Sugihara gave another proof of the theorem based on primitive arguments on Euclidean geometry. Unfortunately, the existing proofs of the the- orem are rather difficult or long. In this paper, we give a simple proof of the theorem characterizing Delaunay graphs, which is based on the fixed point theorem.
  • 松井 知己, 宮本 裕一郎
    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2012 182-183 2012年9月12日  
  • 田中 健一, 宮代 隆平, 宮本 裕一郎
    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2011 198-199 2011年9月13日  

書籍等出版物

 1

講演・口頭発表等

 22

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

 8