![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2020-05-23T10:35:30+09:00","","") #author("2020-06-18T09:54:02+09:00","","") * 研究テーマ [#v400d2d8] いままでに行った研究の紹介をします．これらは「これからやりたい研究」とは異なる可能性があるのでご注意ください． #contents &color(,yellow){''以下，時間があるときに書き足してます．''}; **計算幾何，離散幾何に関する研究 [#k09d96e6] 点，直線，平面のような図形を扱う数学が幾何学 ([[geometry>http://en.wikipedia.org/wiki/Geometry]]) です．図形を計算機でどのように扱うのか考えるのが計算幾何学 ([[computational geometry>http://en.wikipedia.org/wiki/Computational_geometry]]) です．離散幾何学 ([[discrete geometry>http://en.wikipedia.org/wiki/Discrete_geometry]]) はその数学的基礎を与えます． ***多角形領域における最短路検索問題 [#i2ccbe94] #ref(pd3.png,nolink,around,left,50%,); 平面上に多角形領域があり，その内部に多角形障害物がいくつもある状況を考えます．この中の2点を結ぶ最短経路長を素早く計算するにはどうしたらよいでしょうか？ ChiangとMitchellが1999年に与えたデータ構造を用いると，最短経路長を計算する処理をlog nのオーダーに抑えるためには，サイズがnの11乗のオーダーととても大きくなってしまいます．(nは領域の頂点数です．) これに対して，2点が領域の境界上にあるときには，最短経路長の計算処理をlog nのオーダーに抑えても，サイズがnの5乗のオーダーぐらいにしかならないデータ構造を設計しました． #clear &size(8){Sang Won Bae and Yoshio Okamoto, Querying two boundary points for shortest paths in a polygonal domain. Computational Geometry: Theory and Applications 45 (2012) 284-293. [[DOI: 10.1016/j.comgeo.2012.01.012>http://dx.doi.org/10.1016/j.comgeo.2012.01.012]]}; ***多角形領域の直径・半径を計算する多項式時間アルゴリズム [#h30dd62e] #ref(pd2.png,nolink,around,left,20%,); 平面上に多角形領域があり，その内部に多角形障害物がいくつもある状況を考えます．この中の2点を結ぶ最短経路長を考えて，それが最も大きくなる2点のことを直径と呼んでいます．多角形領域における直径計算問題が多項式時間で解けるかどうかは分かっていませんでしたが，この研究によって多項式時間で実際に解けるということが判明しました． また，同様な問題として半径計算問題が知られていますが，これに対してもはじめて多項式時間で解けることが分かりました． #clear &size(8){Sang Won Bae, Matias Korman, and Yoshio Okamoto, The geodesic diameter of polygonal domains. Discrete & Computational Geometry 50 (2013) 306-329. [[DOI:10.1007/s00454-013-9527-8>http://dx.doi.org/10.1007/s00454-013-9527-8]]}; &size(8){Sang Won Bae, Matias Korman, and Yoshio Okamoto, Computing the Geodesic Centers of a Polygonal Domain. Computational Geometry: Theory and Applications 77 (2019) 3-9. [[DOI:10.1016/j.comgeo.2015.10.009>http://dx.doi.org/10.1016/j.comgeo.2015.10.009]]}; ***彫刻庭園問題 [#j7e32085] #ref(sculp1.png,nolink,around,left,20%,); ワイヤレスネットワークにおけるサービス提供の問題に端を発して，2007年にEppsteinらは「彫刻庭園問題」という新しい種類の監視問題を提案しました．これは，平面上に与えられた多角形を記述するために必要なくさび型の数がいくつになるのか，という離散幾何学的な問題として定式化されます．この研究では必要十分な監視員の数を改善し，また，最小の監視員数を計算する最適化問題の計算複雑性も明らかにしました． #clear &size(8){Tobias Christ, Michael Hoffmann, Yoshio Okamoto, and Takeaki Uno, Improved bounds for wireless localization. Algorithmica 57 (2010) 499-516. [[DOI: 10.1007/s00453-009-9287-2>http://dx.doi.org/10.1007/s00453-009-9287-2]]}; &size(8){Tobias Christ, Michael Hoffmann, and Yoshio Okamoto, Natural wireless localization is NP-hard. Abstracts of 25th European Workshop on Computational Geometry, 2009, 175-178.}; ***幾何学的な最大一意被覆問題に対する近似アルゴリズム [#r3f38d04] #ref(uniqcov.png,nolink,around,left,30%,); ワイヤレスネットワークにおいて干渉を考慮しながらサービスをより多く提供する問題を単純化すると最大一意被覆問題という最適化問題になります．この問題において，特に，信号発信基地の覆う領域が単位正方形か単位円である場合を考察して，従来の結果を改善する高速近似アルゴリズムを開発しました． #clear &size(8){Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, A 4.31-approximation for the geometric unique coverage problem on unit disks. Theoretical Computer Science 544 (2014) 14-31. [[DOI:10.1016/j.tcs.2014.04.014>http://dx.doi.org/10.1016/j.tcs.2014.04.014]]}; &size(8){Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno, A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares. Computational Geometry: Theory and Applications 51 (2016) 25-39. [[DOI:10.1016/j.comgeo.2015.10.004>http://dx.doi.org/10.1016/j.comgeo.2015.10.004]]}; ***ミンコフスキー和における凸独立集合 [#o71c1007] #ref(mink.png,nolink,around,left,20%,); 平面上に与えられた2つの点集合の「和」を考えたとき，それが作ることのできる最大頂点数の凸多角形は何なのでしょうか？Eisenbrandらはその大きさに対する上界を与えましたが，その上界を達成するような例が知られていませんでした．この研究ではそのような例を実際に構成しました． #clear &size(8){Ondřej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin-ichi Tanigawa, and Csaba D. Tóth, A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets. The Electronic Journal of Combinatorics 17, N35 (2010), 4 pages. [[Available at EJC page.>http://www.combinatorics.org/Volume_17/Abstracts/v17i1n35.html]]}; ***適応的計算幾何 [#wb1e14bf] #ref(acg.png,nolink,around,left,20%); 入力が既に望む出力に近い場合により早く実行が終了するアルゴリズムを「適応的」と伝統的に呼んできます．この枠組を計算幾何学に適用して，適応的な凸包計算アルゴリズムを実際に設計しました． #clear &size(8){Hee-Kap Ahn and Yoshio Okamoto, Adaptive algorithms for planar convex hull problems. IEICE Transactions on Information and Systems E94-D (2011) 182-189. [[DOI: 10.1587/transinf.E94.D.182>http://dx.doi.org/10.1587/transinf.E94.D.182]]}; ***計算幾何学における固定パラメータ・アルゴリズム [#z449eb0f] #ref(tri.png,nolink,around,left,20%,); 最適化問題の中には，入力が特別な構造を持っていると簡単に解けるものがあります．しかし，そのような解法は特別な構造の性質を十二分に用いるため，そのような構造を持っていない場合には別の方法論を使う必要がでてきます．「固定パラメータ・アルゴリズム」という枠組は入力がそのような構造に近い場合に高速に動くアルゴリズムを開発することを目指します．この枠組を巡回セールスマン問題と最小三角形分割問題に適用しました． #clear &size(8){Michael Hoffmann and Yoshio Okamoto, The minimum weight triangulation problem with few inner points. Computational Geometry: Theory and Applications 34 (2006) 149-158. [[DOI: 10.1016/j.comgeo.2005.11.006>http://dx.doi.org/10.1016/j.comgeo.2005.11.006]]}; &size(8){Vladimir G. Deineko, Michael Hoffmann, Yoshio Okamoto, and Gerhard J. Woeginger, The traveling salesman problem with few inner points, Operations Research Letters 34 (2006) 106--110. [[DOI: 10.1016/j.orl.2005.01.002>http://dx.doi.org/10.1016/j.orl.2005.01.002]]}; ***曲がり角情報から多角形を復元する方法 [#wdc671ac] #ref(turn.png,nolink,around,left,50%,); 正方格子上に頂点を持つ軸平行単純多角形の各頂点における曲がり方を見ます．その曲がり方の列と同じ曲がり方をする多角形の中で面積が最小のものは何になるのでしょうか？ その最悪の場合と最善の場合が何であるか証明しました． #clear &size(8){Sang Won Bae, Yoshio Okamoto, and Chan-Su Shin, Area bounds of rectilinear polygons realized by angle sequences. Lecture Notes in Computer Science 7676 (2012) 629-638. [[DOI: 10.1007/978-3-642-35261-4_65>http://dx.doi.org/10.1007/978-3-642-35261-4_65]]}; &size(8){Sang Won Bae, Yoshio Okamoto, and Chan-Su Shin, Area bounds of rectilinear polygons realized by angle sequences. Computational Geometry: Theory and Applications 83 (2019) 9-29. [[DOI:10.1016/j.comgeo.2019.05.004>http://dx.doi.org/10.1016/j.comgeo.2019.05.004]]}; ***望みの位置を重心とするように錘を置く方法 [#ve8abea8] #ref(invbarycenter.png,nolink,around,left,30%,); 多角形の中の任意の点はその辺上のある3点の重心であるということを証明しました．この「3点」はkが3以上であれば「k点」に拡張することができ，また，そのk点に重みが与えられていて，考える重心が重み付き重心であってもよいです (ただし，そのときの重みは極端に不釣り合いであってはいけません)．そのような3点 (あるいはk点) は効率よく見つけることができます．また，この定理の3次元版も証明しました． #clear &size(8){ Luis Barba, Otfried Cheong, Jean-Lou De Carufel, Michael Gene Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, and Sander Verdonschot, Tianhao Wang, Weight balancing on boundaries and skeletons. Proceedings of 30th Annual Symposium on Computational Geometry (SoCG 2014), 2014, pp. 436-443. [[DOI:10.1145/2582112.2582142>http://dx.doi.org/10.1145/2582112.2582142]]}; **集合族に関する研究 [#m311fc0c] 有限集合の部分集合をいくつか集めたものが集合族 ([[set family>http://en.wikipedia.org/wiki/Family_of_sets]]) です．これだけでは何の研究もできなそうですが，集合族に対して望ましい性質をいろいろと付加することで，そこに構造が生まれていきます．特に，マトロイド ([[matroid>http://en.wikipedia.org/wiki/Matroid]]) やアンチマトロイド ([[antimatroid>http://en.wikipedia.org/wiki/Antimatroid]]) (あるいは，抽象凸幾何 ([[abstract convex geometry>http://en.wikipedia.org/wiki/Antimatroid#Convex_geometries]])) と呼ばれる集合族があり，それらに対する研究をしました．これらは離散幾何学における概念を組合せ的に抽象化したものと考えることができ，さらに，離散最適化において「効率良く解くことのできる問題」が持つ離散構造に関する一般論へと発展していきます． ***グラフのクリーク複体とマトロイド交叉の関係 [#n78320d1] #ref(cc1.png,nolink,around,left,20%,); 無向グラフのクリーク (完全部分グラフの頂点集合) を全部集めてくると，集合族ができます．これがマトロイドと呼ばれる集合族をいくつ持ってきて書けるのか，ということを研究しました．この数は貪欲法や局所探索法によって最大重みクリーク問題を近似的に解くときの精度保証に関係してきます．結果として，分割マトロイドというとてもきれいなマトロイドですべてが記述できることが分かりました． #clear &size(8){Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Uno, Matroid representation of clique complexes, Discrete Applied Mathematics 155 (2007) 1910-1929. [[DOI: 10.1016/j.dam.2007.05.004>http://dx.doi.org/10.1016/j.dam.2007.05.004]]}; ***凸多面体の向き付けと有向マトロイドの実現可能性 [#u6d4c26d] #ref(om1.png,nolink,around,left,20%,); 線形計画問題に対する単体法は凸多面体グラフの向き付けにおける探索であると見なせます．一方，有向マトロイドと呼ばれる集合族があり，それがユークリッド空間内の点配置として実現可能であるのはどういうときか，という問題があります．この研究ではその2つの概念を融合させて，凸多面体グラフの向き付けとして得られない向き付けから，実現可能ではない有向マトロイドを生成する手法を与えました． #clear &size(8){Komei Fukuda, Sonoko Moriyama, and Yoshio Okamoto, The Holt-Klee condition for oriented matroids. European Journal of Combinatorics 30 (2009) 1854-1867. [[DOI: 10.1016/j.ejc.2008.12.012>http://dx.doi.org/10.1016/j.ejc.2008.12.012]]}; ***線形相補性問題に付随する超立方体の向き付け [#v950e340] #ref(swconj.png,nolink,around,left,50%,); 線形計画法や凸二次計画法などを含む線形相補性問題に関する研究です．線形相補性問題は難しい問題 (NP完全問題) として知られているのですが，現れる係数行列が特殊な構造を持つ場合には効率よく解けることが知られています．しかし，どんな構造を持っていると効率よく解けるのかということがよく分かっていません．その重要な場合というのは係数行列がP行列と呼ばれるもののときです．このときには，単体法に似たアルゴリズムで線形相補性問題を解くことができますが，そのピボット演算回数が指数的になることが知られています．そのため，単体法が導く向き付けにどのような構造があるか興味が湧きます．この研究では，向き付けの構造に関するStickneyとWatsonの問題を部分的に解決しました． #clear &size(8){Sonoko Moriyama and Yoshio Okamoto, The even outdegree conjecture for acyclic PLCP-cubes in dimension five. IEICE Transactions on Information and Systems E89-D (2006) 2402-2404. [[DOI:10.1093/ietisy/e89-d.8.2402>http://dx.doi.org/10.1093/ietisy/e89-d.8.2402]]}; ***抽象凸幾何の幾何的表現定理 [#i46cb2c8] #ref(geomrepre.png,nolink,around,left,40%,); 抽象凸幾何は幾何学における凸性を組合せ的に抽象化したものです．しかし，この研究では，抽象凸幾何はすべて幾何学のことばで表現できるということを証明しました．このような表現定理は有向マトロイドやマトロイドでも知られていたのですが，それに対応する定理が抽象凸幾何に対しても得られたということになります． #clear &size(8){Kenji Kashiwabara, Masataka Nakamura, and Yoshio Okamoto, The affine representation theorem for abstract convex geometries, Computational Geometry: Theory and Applications 30 (2005) 129-144. [[DOI:10.1016/j.comgeo.2004.05.001>http://dx.doi.org/10.1016/j.comgeo.2004.05.001]]}; ***抽象凸幾何のトポロジーに関するEdelman-Reiner予想 [#jd84680e] #ref(freetopo.png,nolink,around,left,30%,); ユークリッド空間における有限点集合からある単体的複体が得られるのですが，そのトポロジーをEdelmanとReinerは決定しました．そして，彼らはその結果がより一般的な抽象凸幾何に対して成り立つことを予想しました．この研究では，その予想を部分的に解決しました． #clear &size(8){Yoshio Okamoto, Local topology of the free complex of a two-dimensional generalized convex shelling. Discrete Mathematics 308 (2008) 3836-3846. [[DOI:10.1016/j.disc.2007.07.078>http://dx.doi.org/10.1016/j.disc.2007.07.078]]}; ***アンチマトロイドの分類 [#afe370ad] #ref(lsantimatroid.png,nolink,around,left,30%,); アンチマトロイド (あるいは抽象凸幾何) は幾何学だけではなく，グラフや半順序集合などさまざまな離散構造から生じます．しかし，それらはどれも同じではなく，特殊な性質を持っていることが多いです．そのような性質に基づいてアンチマトロイドを分類するという研究を行いました． #clear &size(8){Yoshio Okamoto and Masataka Nakamura, The forbidden minor characterization of line-search antimatroids of rooted digraphs, Discrete Applied Mathematics 131 (2003) 523-533.[[DOI:10.1016/S0166-218X(02)00471-7>http://dx.doi.org/10.1016/S0166-218X(02)00471-7]]}; **グラフ描画，情報可視化アルゴリズムに関する研究 [#l0af83af] 平面上 (あるいは空間内) にグラフを上手に描く方法を研究するのがグラフ描画 ([[graph drawing>http://en.wikipedia.org/wiki/Graph_drawing]]) という分野です．この分野は「グラフ」と「幾何」の両方に精通している必要があり，また「上手に描く」という人間的な視点も持っているため，独特な味わいを持つ分野になっています．その数学的基礎は幾何学的グラフ理論 ([[geometric graph theory>http://en.wikipedia.org/wiki/Geometric_graph_theory]])，位相幾何学的グラフ理論 ([[topological graph theory>http://en.wikipedia.org/wiki/Topological_graph_theory]]) であり，実世界への応用は情報可視化 ([[information visualization>http://en.wikipedia.org/wiki/Information_visualization]]) として現れます． ***階層構造付きラベル配置問題 [#ldd4a9c9] #ref(ltree.png,nolink,around,left,30%,); 地域の名称のようなラベルを地図に付ける際に，地域の間の階層構造も同時にグラフとして描きたいとします．このときに，そのグラフを上手に描くためにはどうしたらよいでしょうか？この状況において作り出される辺同士の交差角や頂点周りで辺が作る角がどれくらい小さくなりえるか，そして，大きくするにはどうしたらよいか，研究しました． #clear &size(8){Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Yoshio Okamoto, and Andreas Spillner, Vertex angle and crossing angle resolution of leveled tree drawings. Information Processing Letters 112 (2012) 630-635. [[DOI:10.1016/j.ipl.2012.05.006>http://dx.doi.org/10.1016/j.ipl.2012.05.006]]}; ***タングルグラムの描き方 [#e7f99b3c] #ref(tanglegram.png,nolink,around,left,30%,); 2つの異なる手法で得られた進化系統樹を視覚的に比較する際に，タングルグラムと呼ばれる図を用いる手法があります．このタングルグラムを上手に描く方法を計算理論の視点から研究しました． #clear &size(8){Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff, Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability. Algorithmica 62 (2012) 309-332. [[DOI:10.1007/s00453-010-9456-3>http://dx.doi.org/10.1007/s00453-010-9456-3]]}; ***planarityの複雑さ [#t662c3c8] #ref(planarity.jpg,nolink,around,left,30%,); [[planarity>http://www.planarity.net/]]という，グラフ描画に関連するゲームがあります．このゲームの複雑さを離散数学，計算理論の観点から解析しました． #clear &size(8){Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, and Alexander Wolff, Untangling a planar graph. Discrete & Computational Geometry 42 (2009) 542-569. [[DOI:10.1007/s00454-008-9130-6>http://dx.doi.org/10.1007/s00454-008-9130-6]]}; ***平面的グラフに対する普遍的点部分集合 [#qb2a76f1] #ref(univptss.png,nolink,around,left,50%,); 平面的グラフとは平面上に辺交差なく描くことのできるグラフのことですが，そのようなグラフがある特定の点集合を頂点として使うように強制されても，平面上に辺交差なく描くことができるのでしょうか？ そのような点集合の要素数がどこまで大きくなりえるのか，考察しました． #clear &size(8){Patrizio Angelini, Carla Binucci, William Evans, Ferran Hurtado, Giuseppe Liotta Tamara Mchedlidze, Henk Meijer, and Yoshio Okamoto, Universal point subsets for planar graphs. Lecture Notes in Computer Science 7676 (2012) 423-432 [[DOI:10.1007/978-3-642-35261-4_45>http://dx.doi.org/10.1007/978-3-642-35261-4_45]]}; ***平面グラフにおける辺長の自由性 [#p6f3c23f] &size(8){Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba Tóth, Free edge lengths in plane graphs. Proceedings of 30th Annual Symposium on Computational Geometry (SoCG 2014), 2014, pp. 426-435. DOI:10.1145/2582112.2582172}; &size(8){Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba Tóth, Free edge lengths in plane graphs. Discrete & Computational Geometry 54 (2015) 259-289. [[DOI:10.1007/s00454-015-9704-z>http://dx.doi.org/10.1007/s00454-015-9704-z]]}; ***単語間の意味上の近さを考慮したワードクラウドの作成法 [#q826803a] #ref(cloud_437.png,nolink,around,left,25%,); [[Wordle>http://www.wordle.net/]]やブログの[[タグクラウド>http://en.wikipedia.org/wiki/Tag_cloud]]に代表されるワードクラウドは単語の重要度をその出現頻度などによって拡大または縮小し，使用されている単語の集合を視覚的に表示する手法です．この論文では，ワードクラウドで使う単語間の意味上の近さを配置に反映させる手法を提案し，その計算複雑性の解明，および，効率的近似アルゴリズムを開発しました． #clear &size(8){Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt, and Alexander Wolff, Semantic word cloud representations: hardness and approximation algorithms. Proceedings of 11th Latin American Theoretical Informatics Symposium (LATIN 2014), Lecture Notes in Computer Science 8392 (2014) 514-525.}; ***地下鉄路線図における交差数最小化のための厳密アルゴリズム [#w42c8647] #ref(metrouno.png,nolink,around,left,30%,); 鉄道路線図をきれいに描く，という研究が最近盛んに行われています．その中でもアルゴリズムとして未解決な問題が多く存在します．この研究では，1つの経路を多くの路線が共有している時，それらを別々にきれいに描く方法として新しいアルゴリズムを設計しました． #clear &size(8){Yoshio Okamoto, Yuichi Tatsu, and Yushi Uno, Exact and fixed-parameter algorithms for metro-line crossing minimization problems. S. Wismath and A. Wolff (eds.), Proceedings of 21st International Symposium on Graph Drawing (GD 2013), Poster Presentation, Lecture Notes in Computer Science 8242 (2013) 520-521.}; **ゲーム理論に関する研究 [#hd9ae785] ゲーム理論 ([[game theory>http://en.wikipedia.org/wiki/Game_theory]]) の中でも特に協力ゲーム理論 ([[cooperative game theory>http://en.wikipedia.org/wiki/Cooperative_game]]) を計算理論の視点から捉える研究をしています．離散最適化問題から派生する協力ゲームに関連する費用分担問題を計算理論の視点から分析し，その計算複雑度の解明や効率的アルゴリズムの開発をしています． ***コンフリクトのある状況下での費用分担問題 [#d5eff082] #ref(conflict.png,nolink,around,left,50%,); エージェント間のコンフリクトがグラフで表現されているとき，エージェントに対する費用分担法を計算するためのアルゴリズムを設計しました． #clear &size(8){Yoshio Okamoto, Fair cost allocations under conflicts --- a game-theoretic point of view ---. Discrete Optimization 5 (2008) 1-18. [[DOI:10.1016/j.disopt.2007.10.002>http://dx.doi.org/10.1016/j.disopt.2007.10.002]]}; &size(8){Yoshio Okamoto, Submodularity of some classes of the combinatorial optimization games. Mathematical Methods of Operations Research 58 (2003) 131-139. [[DOI:10.1007/s001860300284>http://dx.doi.org/10.1007/s001860300284]]}; ***巡回セールスマン問題に付随する費用分担問題 [#k3dd54f4] #ref(tsg.png,nolink,around,left,50%,); ノーベル賞受賞者をフランスから招待して，インド，韓国，日本で講演をしてもらうとき，その旅費をこの3カ国でどのように分担すれば「公平」だと考えられるでしょうか．この公平費用分担問題の計算複雑性を明らかにし，特殊な場合に対して効率的アルゴリズムを設計しました． #clear &size(8){Yoshio Okamoto, Traveling salesman games with the Monge property, Discrete Applied Mathematics 138 (2004) 349-369. [[DOI:10.1016/j.dam.2003.08.005>http://dx.doi.org/10.1016/j.dam.2003.08.005]]}; ***コア安定性問題に対する計算理論的アプローチ [#b89c1812] #ref(core.png,nolink,around,left,50%,); 協力ゲーム理論における大きな未解決問題に「コア安定性問題」というものがあります．これはコアと呼ばれる集合と安定集合と呼ばれる集合が一致するのはいつなのか，ということを特徴づける問題です．この問題に計算理論の視点からアプローチをして，その計算複雑性に迫りました． #clear &size(8){Thomas Bietenhader and Yoshio Okamoto, Core stability of minimum coloring games. Mathematics of Operations Research 31 (2006) 418-431. [[DOI:10.1287/moor.1060.0187>http://dx.doi.org/10.1287/moor.1060.0187]]}; ***提携構造に制限がある協力ゲームのコア [#a91bf941] #ref(policystr.png,nolink,around,left,50%,); 教科書に書いてあるような協力ゲーム理論では，すべての提携が形成可能であることを暗に仮定しています．しかし，政治的信条や地理的隔離などの理由によって，それが不可能である場合も存在します．そのように形成可能な提携に制限がある場合に，コアと呼ばれる概念がどのように拡張されて，しかも，伝統的な協力ゲームにおいて成り立っていた定理がどのように拡張できるのか，考察しました． #clear &size(8){Yoshio Okamoto, Some properties of the core on convex geometries. Mathematical Methods of Operations Research 56 (2002) 377-386. [[DOI:10.1007/s001860200218>http://dx.doi.org/10.1007/s001860200218]]}; ***最小費用全域木ゲームの劣モジュラ性 [#k73dfdee] &size(8){Masayuki Kobayashi and Yoshio Okamoto, Submodularity of minimum-cost spanning tree games. Networks 63 (2014) 231-238. [[DOI:10.1002/net.21540>http://dx.doi.org/10.1002/net.21540]]}; #clear **数え上げアルゴリズム，列挙アルゴリズムに関する研究 [#r7ac5823] ある性質を満たすものがいくつあるのか計算するのが数え上げ問題 ([[counting problem>http://en.wikipedia.org/wiki/Counting_problem_%28complexity%29]]) で，そのようなものをすべて出力するのが列挙問題 ([[enumeration problem>http://en.wikipedia.org/wiki/Enumeration]]) です．このような問題に対するアルゴリズム設計には特別な方法論が必要となり，また「数え上げによる最適化」という新しい視点を最適化理論に提供することにも成功しています． ***グラフの内部構造の数え上げ [#ea4e1f8c] #ref(indenum.png,nolink,around,left,20%,); 与えられたグラフの中からある性質を満たす部分をすべて数える問題に対して，どのようなグラフクラスに対して効率良く解くことができ，どのようなグラフクラスに対して難しくなるのかということを解明しました．数え上げアルゴリズム理論の礎を築く研究です． #clear &size(8){Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara, Counting the number of independent sets in chordal graphs. Journal of Discrete Algorithms 6 (2008) 229-242. [[DOI: 10.1016/j.jda.2006.07.006>http://dx.doi.org/10.1016/j.jda.2006.07.006]]}; &size(8){Yoshio Okamoto, Ryuhei Uehara, and Takeaki Uno, Counting the number of matchings in chordal and chordal bipartite graph classes. Lecture Notes in Computer Science 5911 (2010) 296-307. [[DOI: 10.1007/978-3-642-11409-0_26>http://dx.doi.org/10.1007/978-3-642-11409-0_26]]}; &size(8){Shuji Kijima, Yoshio Okamoto, and Takeaki Uno, Dominating set counting in graph classes. Lecture Notes in Computer Science 6842 (2011) 13-24. [[DOI:10.1007/978-3-642-22685-4_2>http://dx.doi.org/10.1007/978-3-642-22685-4_2]]}; ***多目的最適化問題に対する多項式時間多項式空間アルゴリズム設計 [#se9c421b] #ref(multiobj.png,nolink,around,left,30%,); 複数の目的関数を同時に最適化しようとする多目的最適化は1つの目的だけを最適化するわけではないため，本質的に列挙問題となっています．最も基本的である多目的線形計画問題に対してさえ，多項式時間多項式空間アルゴリズムが知られていませんでした．この研究では，退化のない多目的線形計画問題に対して，そのパレート端点最適解列挙が多項式時間多項式空間で行えることを証明しました． #clear &size(8){Yoshio Okamoto and Takeaki Uno, A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization. European Journal of Operational Research 210 (2011) 48-56. [[DOI:10.1016/j.ejor.2010.10.008>http://dx.doi.org/10.1016/j.ejor.2010.10.008]]}; ***弦グラフサンドイッチ問題に対する数え上げ，列挙アルゴリズム [#jc993062] #ref(sandwich.png,nolink,around,left,50%,); 数値計算でよくあらわれる疎行列の構造を生かしたアルゴリズム設計や統計学におけるグラフィカルモデルでは，弦グラフというグラフが重要な役割を担っています．与えられた条件を満たす弦グラフを列挙したりランダムに生成できると，それによって，柔軟な最適化を行うことができます．この研究では，その条件が「弦グラフが2つ与えられ，一方に含まれ，もう一方を含む弦グラフである」と表現されるとき，問題がどれほど難しいのか，ということを考察しました． #clear &size(8){Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, and Takeaki Uno, On listing, sampling, and counting the chordal graphs with edge constraints. Theoretical Computer Science 411 (2010) 2591-2601. [[DOI:10.1016/j.tcs.2010.03.024>http://dx.doi.org/10.1016/j.tcs.2010.03.024]]}; ***不完全データからの系統樹復元問題に対するZDDアプローチ [#nde79d64] #ref(zdd.png,nolink,around,left,40%,); 生物進化の道筋を表す系統樹は我々が各時点で生物がどのように進化してきたか記録しているわけではないので，現在得られているデータから復元する以外にその姿を見る方法はありません．そのための方法論がいくつも提案されています．この研究では，データが不完全である場合に効率よく復元をする方法として，[[ゼロサプレス型二分決定木 (ZDD)>http://en.wikipedia.org/wiki/Zero_Suppressed_Decision_Diagram]] を用いた手法を提案しました．それによりナイーブな手法では解けなった問題が解けるようになりました． #clear &size(8){Masashi Kiyomi, Yoshio Okamoto, and Toshiki Saitoh, Efficient enumeration of the directed binary perfect phylogenies from incomplete data. Lecture Notes in Computer Science 7276 (2012) 248-259. [[DOI:10.1007/978-3-642-30850-5_22>http://dx.doi.org/10.1007/978-3-642-30850-5_22]]}; #clear ***グラフのTutte多項式を高速に計算するアルゴリズム [#fdeaba4c] #ref(tutte.png,nolink,around,left,40%,); #clear &size(8){Heidi Gebauer and Yoshio Okamoto, Fast exponential-time algorithms for the forest counting and the Tutte polynomial computation in graph classes. International Journal of Foundations of Computer Science 20 (2009) 25-44. [[DOI:10.1142/S0129054109006437>http://dx.doi.org/10.1142/S0129054109006437]]}; **劣モジュラ最適化に関する研究 [#ef477af0] 離散最適化の研究が進展していくなかで，「効率良く解ける離散最適化問題」に関する理解が深まっています．その中で劣モジュラ関数 ([[submodular function>http://en.wikipedia.org/wiki/Submodular_set_function]]) の果たす役割は大きいと認識されています． ***クラスタリング問題に対する劣モジュラ関数の応用 [#nd43d161] #ref(sc.png,nolink,around,left,20%,); 機械学習に現れるクラスタリング問題への応用として，2つの劣モジュラ関数の比を最小化する問題を考えて，「離散ニュートン法」というアルゴリズムの枠組を提案しました．劣モジュラ関数という抽象的な枠組でアルゴリズムを構築しているため，汎用性や柔軟性に富みますが，それでもなお，アルゴリズムにおける反復回数を理論的に抑えることができました．計算機実験により，従来手法よりもよいクラスタリングが可能になることが分かりました． #clear &size(8){Yoshinobu Kawahara, Kiyohito Nagano, and Yoshio Okamoto, Submodular fractional programming for balanced clustering. Pattern Recognition Letters 32 (2011) 235-243. [[DOI: 10.1016/j.patrec.2010.08.008>http://dx.doi.org/10.1016/j.patrec.2010.08.008]]}; ***抽象凸幾何上への劣モジュラ関数の拡張 [#c2ea9ff2] #ref(csub.png,nolink,around,left,60%,); 劣モジュラ関数は分配束という単純な離散構造上に定義される関数ですが，それをより複雑な集合族である抽象凸幾何上で定義できるように拡張しました．このとき，劣モジュラ関数が定める多面体上での線形計画問題が貪欲法によって解ける，という性質も保つことができ，効率良く解ける離散最適化問題のクラスが広がりました． #clear &size(8){Kenji Kashiwabara and Yoshio Okamoto, A greedy algorithm for convex geometries. Discrete Applied Mathematics 131 (2003) 449-465. [[DOI: 10.1016/S0166-218X(02)00467-5>http://dx.doi.org/10.1016/S0166-218X(02)00467-5]]}; **計算複雑性に関する研究 [#y6492341] アルゴリズムの設計や解析を行っているとき，自分の設計したアルゴリズムをもっとよいものにできないかと考えるものです．しかし，計算複雑性理論 ([[computational complexity theory>http://en.wikipedia.org/wiki/Computational_complexity_theory]]) に基づくと，そのような性能向上にはある限界があることが知られています．別の言い方をすると，そのような限界を知ることで，設計したアルゴリズムがどれほど「究極のアルゴリズム」に近いのか分かることになります． ***強指数時間仮説と指数時間厳密アルゴリズム存在性の関係を導く新たな帰着法 [#w558991e] #ref(seth.png,nolink,around,left,50%,); 充足可能性問題 (SAT) は出現する変数の数がnであるとき，2のn乗ぐらいの時間で解くことは簡単にできます．しかし，これが1.99のn乗ぐらいの時間で解けるかどうか知られていません．それが可能ではない，というのが「強指数時間仮説 (strong [[exponential-time hypothesis>http://en.wikipedia.org/wiki/Exponential_time_hypothesis]])」のおおまかな意味です．この仮説に基づいて，他の最適化問題に同じような不可能性が導かれることを証明しました．そのためは計算複雑性理論でよく用いられる帰着を使いますが，いままでよりもある意味で強い帰着が必要となり，それがこの研究の主眼となっています． #clear &size(8){Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström, On problems as hard as CNF-SAT. Proceedings of 27th IEEE Conference on Computational Complexity (CCC 2012), 2012, pp. 74-84. [[DOI:10.1109/CCC.2012.36>http://dx.doi.org/10.1109/CCC.2012.36]]}; &size(8){Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström, On problems as hard as CNF-SAT. ACM Transactions on Algorithms 12(3), Article No. 41, 2016. [[DOI:10.1145/2925416>http://dx.doi.org/10.1145/2925416]]}; **グラフアルゴリズム，グラフ理論に関するその他の研究 [#f88d4e43] ここにはグラフアルゴリズムやグラフ理論に関するその他の論文が並んでいます．まとまった内容のものが集まったときにはその部分を独立した節にします． ***二部グラフの二部冪 [#u1a8b566] #ref(bipow.png,nolink,around,left,20%,); グラフGのk冪とは，Gにおいて長さk以下のパスで結ばれる2頂点を辺で結んでできるグラフのことであり，いろいろな性質が知られています．この研究では，二部グラフの二部k冪という概念を掘り下げ，計算複雑性の解明や，ある種のグラフクラスにおいて閉じているという性質を発見しました． #clear &size(8){Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara, On bipartite powers of bigraphs. Discrete Mathematics & Theoretical Computer Science 14(2) (2012) 11-20. http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2132}; ***単位格子交差グラフと弦二部グラフの関係 [#u7251933] #ref(uig.png,nolink,around,left,20%,); 平面上の東西方向または南北方向に伸びる単位直線分の交差パターンとして得られる単位格子交差グラフと弦二部グラフの関係を調べました．特に，弦二部グラフであるが，単位格子交差グラフではないものの例を発見しました． #clear &size(8){Yota Otachi, Yoshio Okamoto, and Koichi Yamazaki, Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs. Discrete Applied Mathematics 155 (2007) 2383-2390. [[DOI: 10.1016/j.dam.2007.07.010>http://dx.doi.org/10.1016/j.dam.2007.07.010]]}; &size(8){Yota Otachi, Yoshio Okamoto, and Koichi Yamazaki, Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs. Discrete Applied Mathematics 155 (2007) 2383-2390. [[DOI:10.1016/j.dam.2007.07.010>http://dx.doi.org/10.1016/j.dam.2007.07.010]]}; ***最大辺素パス問題に対する近似アルゴリズム [#m81936bb] #ref(medp.png,nolink,around,left,30%,); #clear &size(8){Paz Carmi, Thomas Erlebach, and Yoshio Okamoto, Greedy edge-disjoint paths in complete graphs. Lecture Notes in Computer Science 2880 (2003) 143-155.[[DOI:10.1007/978-3-540-39890-5_13>http://dx.doi.org/10.1007/978-3-540-39890-5_13]]}; ***嘘を含む比較を用いた最小値最大値発見アルゴリズム [#d1b27328] #ref(maxminlie.png,nolink,around,left,50%,); 間違える可能性のある比較を用いて最大値と最小値を同時に計算する問題に対して，ネットワーク流の考え方を用いることで，既存の手法よりも少ない比較回数で計算できる方法を開発しました． #clear &size(8){Michael Hoffmann, Jiri Matousek, Yoshio Okamoto, and Philipp Zumstein, Minimum and maximum against k lies. Chicago Journal of Theoretical Computer Science 2012 (2012), Article 2, pp. 1-10. [[DOI:10.4086/cjtcs.2012.002>http://dx.doi.org/10.4086/cjtcs.2012.002]]}; ***全域木混雑度計算の複雑性と指数時間厳密アルゴリズム [#n9dc6c99] #ref(stc.png,nolink,around,left,50%,); ネットワークの性能を評価する全域木混雑度という新しい指標に関して，その計算複雑性を解明し，高速な指数時間厳密アルゴリズムを開発しました． #clear &size(8){Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno, Hardness results and an exact exponential algorithm for the spanning tree congestion problem. [[Journal of Graph Algorithms and Applications 15 (2011) 727-751>http://jgaa.info/getPaper?id=246]]}; ***道距離幅に対する近似アルゴリズム [#j38d3da6] #ref(pdw.jpg,nolink,around,left,60%,); グラフの構造のよさを表す指標がいくつか提案されていますが，道距離幅もその1つです．与えられたグラフの道距離幅を計算する問題の難しさを解明し，それに対して理論保証のある近似アルゴリズムを設計しました． #clear &size(8){Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, and Koichi Yamazaki, Approximating the path-distance-width for AT-free graphs and graphs in related classes. Discrete Applied Mathematics 168 (2014) 69-77. [[DOI:10.1016/j.dam.2012.11.015>http://dx.doi.org/10.1016/j.dam.2012.11.015]]}; ***トーラスの茨数 [#y353c4ee] #ref(bramble.png,nolink,around,left,60%,); #clear &size(8){Masashi Kiyomi, Yoshio Okamoto, Yota Otachi, On the treewidth of toroidal grids. Proceedings of JCDCGG 2013, 2 pages}; &size(8){Masashi Kiyomi, Yoshio Okamoto, and Yota Otachi, On the treewidth of toroidal grids. Discrete Applied Mathematics 198 (2016) 303-306. [[DOI:10.1016/j.dam.2015.06.027>http://dx.doi.org/10.1016/j.dam.2015.06.027]]}; ***ランダムネットワークにおける情報拡散 [#kb484ee3] #ref(toyoizumi.png,nolink,around,left,50%,); 社会ネットワークのようにランダムに生成された (と思われる) ネットワークにおいて効率よく情報を拡散するにはどうしたらよいでしょうか？ 各ノードの隣接ノードに反比例する確率で拡散する方法の効率を調べて，ハブと呼ばれるノードが拡散におけるボトルネックとならないようにしました． #clear &size(8){Hiroshi Toyoizumi, Seiichi Tani, Naoto Miyoshi, and Yoshio Okamoto, Reverse preferential spread in complex networks. Physical Review E 86, 021103 (2012), 6 pages. [[DOI:10.1103/PhysRevE.86.021103>http://dx.doi.org/10.1103/PhysRevE.86.021103]]}; **組合せゲーム，パズルに関する研究 [#cf94c886] ***浮き出し迷路の作成法 [#j9e251ca] #ref(maze.jpg,nolink,around,left,30%,); 解いた後に絵が浮き出る迷路を「浮き出し迷路」と呼んだりします．浮かび上がらせたい絵を入力したときに，それを答えとするような迷路を自動的に作成する単純なアルゴリズムを提案しました．これは，連結でさえあればどんな絵でも入力として受け付けて，線形時間 (つまり高速) に迷路を作成します．グラフにおける全域木のランダム生成とオイラー閉路という基本的な道具しか用いていないところがセールスポイントです． #clear &size(8){Yoshio Okamoto, and Ryuhei Uehara, How to make a picturesque maze. Proceedings of 21st Canadian Conference on Computational Geometry (CCCG 2009), 137-140.}; ***シャカシャカの計算複雑性と整数計画モデル [#i6129b72] #ref(shakashaka.png,nolink,around,left,50%,); #clear &size(8){Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno, Computational complexity and an integer programming model of Shakashaka. Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013).}; &size(8){Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno, Computational complexity and an integer programming model of Shakashaka, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97-A (2014) 1213-1219. [[DOI:10.1587/transfun.E97.A.1213>http://dx.doi.org/10.1587/transfun.E97.A.1213]]}; ***重み付きグラフにおける石移動ゲーム [#m81936bb] #ref(peb.png,nolink,around,left,20%,); #clear &size(8){Michael Hoffmann, Jiri Matousek, Yoshio Okamoto, Philipp Zumstein, The t-pebbling number is eventually linear in t. The Electronic Journal of Combinatorics 18(1), P153 (2011), 4 pages. [[The Electronic Journal of Combinatorics 18(1), P153 (2011)>http://www.combinatorics.org/Volume_18/Abstracts/v18i1p153.html]]}; * 教員の発表論文 [#i4dfcb39] [[こちら>http://dopal.cs.uec.ac.jp/okamotoy/research/]] (英語) をご覧下さい． RIGHT:(文責：岡本吉央)
