岡本 吉央
| 情報・ネットワーク工学専攻 | 教授 |
| Ⅰ類（情報系） | 教授 |
研究者情報
研究分野
経歴
- 2017年04月01日
電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 教授 - 2016年04月01日 - 2017年03月31日
電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 准教授 - 2012年04月01日 - 2016年03月31日
電気通信大学, 大学院情報理工学研究科 情報・通信工学専攻, 准教授 - 2010年10月01日 - 2012年03月31日
北陸先端科学技術大学院大学, 大学院教育イニシアティブセンター, 特任准教授 - 2007年12月01日 - 2010年09月30日
東京工業大学, 大学院情報理工学研究科, 特任准教授 - 2007年04月01日 - 2007年11月30日
豊橋技術科学大学, 工学部 情報工学系, 助教 - 2005年04月01日 - 2007年03月31日
豊橋技術科学大学, 工学部 情報工学系, 助手
研究活動情報
受賞
- 受賞日 2022年03月
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会フェロー - 受賞日 2021年09月
船井ベストペーパー賞, 岡本吉央;伊藤健洋;垣村尚徳;神山直之;小林佑輔
国内学会・会議・シンポジウム等の賞 - 受賞日 2020年09月
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会第10回研究賞
国内学会・会議・シンポジウム等の賞 - 受賞日 2015年
日本ソフトウェア科学会
日本ソフトウェア科学会第5回解説論文賞, 横尾真;岩崎敦;櫻井祐子;岡本吉央
国内学会・会議・シンポジウム等の賞 - 受賞日 2012年
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会研究賞奨励賞 - 受賞日 2010年
EATCS, LA Symposium
8th EATCS/LA Presentation Award - 受賞日 2004年
Editors' Choice 2003, Discrete Applied Mathematics
論文
- Minimum Separator Reconfiguration
Guilherme C. M. Gomes; Clément Legrand-Duchesne; Reem Mahmoud; Amer E. Mouawad; Yoshio Okamoto; Vinícius Fernandes dos Santos; Tom C. van; der Zanden
18th International Symposium on Parameterized and Exact Computation (IPEC 2023), 掲載ページ 9:1-9:12, 出版日 2023年12月, 査読付
研究論文（国際会議プロシーディングス） - On reachable assignments under dichotomous preferences
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
Theoretical Computer Science, Elsevier BV, 979巻, 掲載ページ 114196-114196, 出版日 2023年11月, 査読付
研究論文（学術雑誌） - Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-Ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), 19巻, 1号, 掲載ページ 1-22, 出版日 2023年01月31日, 査読付
研究論文（学術雑誌） - Graphs with large total angular resolution
Oswin Aichholzer; Matias Korman; Yoshio Okamoto; Irene Parada; Daniel Perz; André van Renssen; Birgit Vogtenhuber
Theoretical Computer Science, Elsevier BV, 943巻, 掲載ページ 73-88, 出版日 2023年01月, 査読付
研究論文（学術雑誌） - On Reachable Assignments Under Dichotomous Preferences
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
PRIMA 2022: Principles and Practice of Multi-Agent Systems, Springer International Publishing, 掲載ページ 650-658, 出版日 2022年11月, 査読付
論文集(書籍)内論文 - Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady; Mark de Berg; Karl Bringmann; Kevin Buchin; Henning Fernau; Dan Halperin; Irina Kostitsyna; Yoshio Okamoto; Stijn Slot
Proceedings of 38th International Symposium on Computational Geometry (SoCG 2022), 掲載ページ 12:1-12:16, 出版日 2022年06月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Weight balancing on boundaries
Luis Barba; Otfried Cheong; Michael Gene Dobbins; Rudolf Fleischer; Akitoshi Kawamura; Matias Korman; Yoshio Okamoto; Janos Pach; Yuan Tang; Takeshi Tokuyama; Sander Verdonschot
Journal of Computational Geometry, 13巻, 1号, 掲載ページ 1-12, 出版日 2022年06月, 査読付, 国際共著論文
英語 - Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
SIAM Journal on Discrete Mathematics, Society for Industrial & Applied Mathematics (SIAM), 36巻, 2号, 掲載ページ 1102-1123, 出版日 2022年06月, 査読付
研究論文（学術雑誌） - A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Operations Research Letters, Elsevier BV, 出版日 2022年05月, 査読付
研究論文（学術雑誌） - Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
SODA, 掲載ページ 1342-1355, 出版日 2022年01月, 査読付
研究論文（国際会議プロシーディングス） - Submodular reassignment problem for reallocating agents to tasks with synergy effects
Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Discrete Optimization, Elsevier BV, 掲載ページ 100631-100631, 出版日 2021年02月, 査読付
研究論文（学術雑誌） - ClusterSets: Optimizing planar clusters in categorical point data
Jakob Geiger; Sabine Cornelsen; Jan-Henrik Haunert; Philipp Kindermann; Tamara Mchedlidze; Martin Nöllenburg; Yoshio Okamoto; Alexander Wolff
Proceedings of 23rd EG Conference on Visualization (EuroVis 2021), Computer Graphics Forum, 40巻, 掲載ページ 471-481, 出版日 2021年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
Elena Arseneva; Man-Kwun Chiu; Matias Korman; Aleksandar Markovic; Yoshio Okamoto; Aurélien Ooms; André van Renssen; Marcel Roeloffzen
Computational Geometry: Theory and Applications, 92巻, 掲載ページ 58:1-58:13, 出版日 2021年, 査読付
研究論文（学術雑誌）, 英語 - Algorithmic enumeration of surrounding polygons
Katsuhisa Yamanaka; David Avis; Takashi Horiyama; Yoshio Okamoto; Ryuhei Uehara; Tanami Yamauchi
Discrete Applied Mathematics, Elsevier BV, 出版日 2020年04月, 査読付
研究論文（学術雑誌） - Subgraph Isomorphism on Graph Classes that Exclude a Substructure
Hans L. Bodlaender; Tesshu Hanaka; Yoshio Okamoto; Yota Otachi; Tom C. van; der Zanden
Proceedings of 11th International Conference on Algorithms and Complexity (CIAC 2019), Springer, 82巻, 12号, 掲載ページ 87-98, 出版日 2019年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Graphs with Large Total Angular Resolution
Oswin Aichholzer; Matias Korman; Yoshio Okamoto; Irene Parada; Daniel Perz; André van Renssen; Birgit Vogtenhuber
Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), 掲載ページ 193-199, 出版日 2019年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Variants of the Segment Number of a Graph
Yoshio Okamoto; Alexander Ravsky; Alexander Wolff
Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), 掲載ページ 430-443, 出版日 2019年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
27th Annual European Symposium on Algorithms(ESA), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 掲載ページ 61-15, 出版日 2019年, 査読付
研究論文（国際会議プロシーディングス） - Computing the Geodesic Centers of a Polygonal Domain
Sang Won Bae; Matias Korman; Yoshio Okamoto
Computational Geometry: Theory and Applications, 77巻, 掲載ページ 3-9, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Minimum-Cost b-Edge Dominating Sets on Trees.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
Algorithmica, 81巻, 1号, 掲載ページ 343-366, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takashi Horiyama; Akitoshi Kawamura; Shin-Ichi Nakano; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Ryuhei Uehara; Takeaki Uno
Journal of Graph Algorithms and Applications, 23巻, 1号, 掲載ページ 3-27, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Reconfiguration of maximum-weight b-matchings in a graph.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
J. Comb. Optim., 37巻, 2号, 掲載ページ 454-464, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Area bounds of rectilinear polygons realized by angle sequences
Sang Won Bae; Yoshio Okamoto; Chan-Su Shin
Computational Geometry: Theory and Applications, 83巻, 掲載ページ 9-29, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Algorithms for Gerrymandering over Graphs.
Takehiro Ito; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), International Foundation for Autonomous Agents and Multiagent Systems, 掲載ページ 1413-1421, 出版日 2019年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
CoRR, abs/1907.01700巻, 掲載ページ 61:1-61:15, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Tight Approximability of the Server Allocation Problem for Real-Time Applications
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto; Taichi Shiitada
Algorithmic Aspects of Cloud Computing, Springer International Publishing, 掲載ページ 41-55, 出版日 2018年, 査読付
論文集(書籍)内論文, 英語 - Exact Algorithms for the Max-Min Dispersion Problem.
Toshihiro Akagi; Tetsuya Araki; Takashi Horiyama; Shin-Ichi Nakano; Yoshio Okamoto; Yota Otachi; Toshiki Saitoh; Ryuhei Uehara; Takeaki Uno; Kunihiro Wasa
Proceedings of 12th International Frontiers of Algorithmics Workshop (FAW 2018), Springer, 掲載ページ 263-272, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Computational Complexity of Robot Arm Simulation Problems
Tianfeng Feng; Takashi Horiyama; Yoshio Okamoto; Yota Otachi; Toshiki Saitoh; Takeaki Uno; Ryuhei Uehara
Proceedings of 29th International Workshop on Combinational Algorithms (IWOCA 2018), Springer, 掲載ページ 177-188, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity
Evmorfia Argyriou; Sabine Cornelsen; Henry Förster; Michael Kaufmann; Martin Nöllenburg; Yoshio Okamoto; Chrysanthi Raftopoulou; Alexander Wolff
Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), 掲載ページ 509-523, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Folding free-space diagrams: Computing the Fréchet distance between 1-dimensional curves
Kevin Buchin; Jinhee Chun; Maarten Löffler; Aleksandar Markovic; Wouter Meulemans; Yoshio Okamoto; Taichi Shiitada
Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 77巻, 掲載ページ 641-645, 出版日 2017年06月01日, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Efficient stabilization of cooperative matching games
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 677巻, 掲載ページ 69-82, 出版日 2017年05月, 査読付
研究論文（学術雑誌）, 英語 - Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain
Sang Won Bae; Matias Korman; Joseph S. B. Mitchell; Yoshio Okamoto; Valentin Polishchuk; Haitao Wang
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, 57巻, 3号, 掲載ページ 674-701, 出版日 2017年04月, 査読付
研究論文（学術雑誌）, 英語 - General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction
Akinori Kawachi; Yoshio Okamoto; Keisuke Tanaka; Kenji Yasunaga
COMPUTER JOURNAL, OXFORD UNIV PRESS, 60巻, 5号, 掲載ページ 711-728, 出版日 2017年04月, 査読付
研究論文（学術雑誌）, 英語 - Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takashi Horiyama; Akitoshi Kawamura; Shin-ichi Nakano; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Ryuhei Uehara; Takeaki Uno
WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, SPRINGER INTERNATIONAL PUBLISHING AG, 10167巻, 掲載ページ 435-447, 出版日 2017年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Takashi Horiyama; Takashi Iizuka; Masashi Kiyomi; Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno; Yushi Uno; Yukiko Yamauchi
Journal of Information Processing, 25巻, 8号, 掲載ページ 708-715, 出版日 2017年, 査読付
研究論文（学術雑誌）, 英語 - Balanced line separators of unit disk graphs
Paz Carmi; Man Kwun Chiu; Matthew J. Katz; Matias Korman; Yoshio Okamoto; André Van Renssen; Marcel Roeloffzen; Taichi Shiitada; Shakhar Smorodinsky
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10389巻, 掲載ページ 241-252, 出版日 2017年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Reconfiguration of maximum-weight b-matchings in a graph
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10392巻, 掲載ページ 287-296, 出版日 2017年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Extended formulations for sparsity matroids
Satoru Iwata; Naoyuki Kamiyama; Naoki Katoh; Shuji Kijima; Yoshio Okamoto
MATHEMATICAL PROGRAMMING, SPRINGER HEIDELBERG, 158巻, 1-2号, 掲載ページ 565-574, 出版日 2016年07月, 査読付
研究論文（学術雑誌）, 英語 - Computational Complexity of Sequential Token Swapping Problem (コンピュテーション)
山中 克久; ドメイン エリック; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 電子情報通信学会, 116巻, 116号, 掲載ページ 115-121, 出版日 2016年06月24日
英語 - シーケンシャルな交換による色付きトークン整列問題の計算複雑さ
山中 克久; エリック ドメイン; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
第158回アルゴリズム研究会, 掲載ページ 1-7, 出版日 2016年06月
研究論文（研究会，シンポジウム資料等）, 日本語 - On Problems as Hard as CNF-SAT
Marek Cygan; Holger Dell; Daniel Lokshtanov; Daniel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh; Magnus Wahlstrom
ACM TRANSACTIONS ON ALGORITHMS, ASSOC COMPUTING MACHINERY, 12巻, 3号, 出版日 2016年06月, 査読付
研究論文（学術雑誌）, 英語 - A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
Takehiro Ito; Shin-ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, ELSEVIER SCIENCE BV, 51巻, 掲載ページ 25-39, 出版日 2016年01月, 査読付
研究論文（学術雑誌）, 英語 - On the treewidth of toroidal grids
Masashi Kiyomi; Yoshio Okamoto; Yota Otachi
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 198巻, 掲載ページ 303-306, 出版日 2016年01月, 査読付
研究論文（学術雑誌）, 英語 - Efficient Stabilization of Cooperative Matching Games
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Proceedings of 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2016), 掲載ページ 41-49, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Approximation and Hardness of Token Swapping
Tillmann Miltzow; Lothar Narins; Yoshio Okamoto; Günter Rote; Antonis Thomas; Takeaki Uno
Proceedings of 24th European Symposium on Algorithms (ESA 2016), 掲載ページ 66:1-66:15, 出版日 2016年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Computing the L-1 geodesic diameter and center of a simple polygon in linear time
Sang Won Bae; Matias Korman; Yoshio Okamoto; Haitao Wang
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, ELSEVIER SCIENCE BV, 48巻, 6号, 掲載ページ 495-505, 出版日 2015年08月, 査読付
研究論文（学術雑誌）, 英語 - Free Edge Lengths in Plane Graphs
Zachary Abel; Robert Connelly; Sarah Eisenstat; Radoslav Fulek; Filip Moric; Yoshio Okamoto; Tibor Szabo; Csaba D. Toth
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, 54巻, 1号, 掲載ページ 259-289, 出版日 2015年07月, 査読付
研究論文（学術雑誌）, 英語 - Swapping labeled tokens on graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takehiro Ito; Jun Kawahara; Masashi Kiyomi; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Kei Uchizawa; Takeaki Uno
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 586巻, 掲載ページ 81-94, 出版日 2015年06月, 査読付
研究論文（学術雑誌）, 英語 - Polynomial-time approximability of the k-Sink Location problem.
Rémy Belmonte; Yuya Higashikawa; Naoki Katoh; Yoshio Okamoto
CoRR, abs/1503.02835巻, 出版日 2015年 - A 4.31-approximation for the geometric unique coverage problem on unit disks
Takehiro Ito; Shin-ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 544巻, 掲載ページ 14-31, 出版日 2014年08月, 査読付
研究論文（学術雑誌）, 英語 - Computational Complexity and an Integer Programming Model of Shakashaka
Erik D. Demaine; Yoshio Okamoto; Ryuhei Uehara; Yushi Uno
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E97A巻, 6号, 掲載ページ 1213-1219, 出版日 2014年06月, 査読付
研究論文（学術雑誌）, 英語 - Submodularity of minimum-cost spanning tree games
Masayuki Kobayashi; Yoshio Okamoto
NETWORKS, WILEY, 63巻, 3号, 掲載ページ 231-238, 出版日 2014年05月, 査読付
研究論文（学術雑誌）, 英語 - Approximating the path-distance-width for AT-free graphs and graphs in related classes
Yota Otachi; Toshiki Saitoh; Katsuhisa Yamanaka; Shuji Kijima; Yoshio Okamoto; Hirotaka Ono; Yushi Uno; Koichi Yamazaki
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 168巻, 掲載ページ 69-77, 出版日 2014年05月, 査読付
研究論文（学術雑誌）, 英語 - グラフ上のラベル付きトークン整列問題
山中 克久; エリック; ドメイン(MIT; 伊藤 健洋; 川原純; 清見 礼; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 内澤 啓; 宇野 毅明(N
電子情報通信学会コンピュテーション研究会資料, 2014巻, 2号, 掲載ページ 5-12, 出版日 2014年04月
研究論文（研究会，シンポジウム資料等）, 日本語 - Computing the L-1 Geodesic Diameter and Center of a Simple Polygon in Linear Time
Sang Won Bae; Matias Korman; Yoshio Okamoto; Haitao Wang
LATIN 2014: THEORETICAL INFORMATICS, SPRINGER-VERLAG BERLIN, 8392巻, 掲載ページ 120-131, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Semantic Word Cloud Representations: Hardness and Approximation Algorithms
Lukas Barth; Sara Irina Fabrikant; Stephen G. Kobourov; Anna Lubiw; Martin Noellenburg; Yoshio Okamoto; Sergey Pupyrev; Claudio Squarcella; Torsten Ueckerdt; Alexander Wolff
LATIN 2014: THEORETICAL INFORMATICS, SPRINGER-VERLAG BERLIN, 8392巻, 掲載ページ 514-525, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Free edge lengths in plane graphs
Zachary Abel; Robert Connelly; Sarah Eisenstat; Radoslav Fulek; Filip Morić; Yoshio Okamoto; Tibor Szabó; Csaba D. Tóth
Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, 掲載ページ 426-435, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Weight balancing on boundaries and Skeletons
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; Sander Verdonschot; Tianhao Wang
Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, 掲載ページ 436-443, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Takashi Horiyama; Masashi Kiyomi; Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno; Yushi Uno; Yukiko Yamauchi
FUN WITH ALGORITHMS, SPRINGER-VERLAG BERLIN, 8496巻, 掲載ページ 230-239, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Swapping Labeled Tokens on Graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takehiro Ito; Jun Kawahara; Masashi Kiyomi; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Kei Uchizawa; Takeaki Uno
FUN WITH ALGORITHMS, SPRINGER-VERLAG BERLIN, 8496巻, 掲載ページ 364-375, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Minimum-Cost b-Edge Dominating Sets on Trees
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
ALGORITHMS AND COMPUTATION, ISAAC 2014, SPRINGER-VERLAG BERLIN, 8889巻, 掲載ページ 195-207, 出版日 2014年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - The Geodesic Diameter of Polygonal Domains
Sang Won Bae; Matias Korman; Yoshio Okamoto
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, 50巻, 2号, 掲載ページ 306-329, 出版日 2013年09月, 査読付
研究論文（学術雑誌）, 英語 - The complexity of the stamp folding problem
Takuya Umesato; Toshiki Saitoh; Ryuhei Uehara; Hiro Ito; Yoshio Okamoto
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 497巻, 掲載ページ 13-19, 出版日 2013年07月, 査読付
研究論文（学術雑誌）, 英語 - Exact and fixed-parameter algorithms for metro-line crossing minimization problems
Yoshio Okamoto; Yuichi Tatsu; Yushi Uno
Proceedings of 21st International Symposium on Graph Drawing (GD 2013), 掲載ページ 520-521, 出版日 2013年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Querying two boundary points for shortest paths in a polygonal domain
Sang Won Bae; Yoshio Okamoto
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, ELSEVIER SCIENCE BV, 45巻, 7号, 掲載ページ 284-293, 出版日 2012年08月, 査読付
研究論文（学術雑誌）, 英語 - Vertex angle and crossing angle resolution of leveled tree drawings
Walter Didimo; Michael Kaufmann; Giuseppe Liotta; Yoshio Okamoto; Andreas Spillner
INFORMATION PROCESSING LETTERS, ELSEVIER SCIENCE BV, 112巻, 16号, 掲載ページ 630-635, 出版日 2012年08月, 査読付
研究論文（学術雑誌）, 英語 - Reverse preferential spread in complex networks
Hiroshi Toyoizumi; Seiichi Tani; Naoto Miyoshi; Yoshio Okamoto
PHYSICAL REVIEW E, AMER PHYSICAL SOC, 86巻, 2号, 出版日 2012年08月, 査読付
研究論文（学術雑誌）, 英語 - 単位正方形上の一意被覆問題に対する近似アルゴリズム
伊藤 健洋; 中野 眞一; 岡本 吉央; 大舘 陽太; 上原 隆平; 宇野 毅明; 宇野 裕之
電子情報通信学会コンピュテーション研究会, 掲載ページ 95-101, 出版日 2012年06月
研究論文（研究会，シンポジウム資料等）, 英語 - Guest editors' foreword
Otfried Cheong; Yoshio Okamoto
International Journal of Computational Geometry and Applications, 22巻, 1号, 掲載ページ 1-2, 出版日 2012年02月, 査読付
研究論文（学術雑誌）, 英語 - Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability
Kevin Buchin; Maike Buchin; Jaroslaw Byrka; Martin Noellenburg; Yoshio Okamoto; Rodrigo I. Silveira; Alexander Wolff
ALGORITHMICA, SPRINGER, 62巻, 1-2号, 掲載ページ 309-332, 出版日 2012年02月, 査読付
研究論文（学術雑誌）, 英語 - Game Theory for Computer Scientists -Noncoop-erative Games (Advanced)-.
Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai; Yoshio Okamoto
Computer Software, 29巻, 3号, 掲載ページ 39-53, 出版日 2012年, 査読付
研究論文（学術雑誌）, 英語 - Efficient enumeration of the directed binary perfect phylogenies from incomplete data
Masashi Kiyomi; Yoshio Okamoto; Toshiki Saitoh
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7276巻, 掲載ページ 248-259, 出版日 2012年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
Takehiro Ito; Shin-Ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7357巻, 掲載ページ 24-35, 出版日 2012年, 査読付, We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen (2009) before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. © 2012 Springer-Verlag.
研究論文（国際会議プロシーディングス）, 英語 - On Problems as Hard as CNF-SAT
Marek Cygan; Holger Dell; Daniel Lokshtanov; Daniel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh; Magnus Wahlstroem
2012 IEEE 27TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), IEEE, 掲載ページ 74-84, 出版日 2012年, 査読付, The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET and 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2(n)), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2(n)), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every epsilon < 1, there is a (large) integer k such that that K-CNF-SAT cannot be computed in time 2(epsilon n).
In this paper, we show that, for every epsilon < 1, the problems HITTING SET, SET SPLITTING, and NAE-SAT cannot be computed in time O(2(epsilon n)) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINTER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers cannot be computed in time O(2(epsilon n)) for any epsilon < 1 unless SETH fails.
研究論文（国際会議プロシーディングス）, 英語 - Minimum and maximum against k lies
Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp; Zumstein
Chicago Journal of Theoretical Computer Science, 2012巻, 2号, 掲載ページ 1-10, 出版日 2012年, 査読付
研究論文（学術雑誌）, 英語 - On bipartite powers of bigraphs
Yoshio Okamoto; Yota Otachi; Ryuhei Uehara
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 14巻, 2号, 掲載ページ 11-20, 出版日 2012年, 査読付, The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.
研究論文（学術雑誌）, 英語 - A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks
Takehiro Ito; Shin-ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
ALGORITHMS AND COMPUTATION, ISAAC 2012, SPRINGER-VERLAG BERLIN, 7676巻, 掲載ページ 372-381, 出版日 2012年, 査読付, We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 + 4/root 3 + epsilon (< 4.3095 + epsilon) for any fixed constant epsilon > 0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.
研究論文（国際会議プロシーディングス）, 英語 - Universal Point Subsets for Planar Graphs
Patrizio Angelini; Carla Binucci; William Evans; Ferran Hurtado; Giuseppe Liotta; Tamara Mchedlidze; Henk Meijer; Yoshio Okamoto
ALGORITHMS AND COMPUTATION, ISAAC 2012, SPRINGER-VERLAG BERLIN, 7676巻, 掲載ページ 423-432, 出版日 2012年, 査読付, A set S of k points in the plane is a universal point subset for a class G of planar graphs if every graph belonging to G admits a planar straight-line drawing such that k of its vertices are represented by the points of S. In this paper we study the following main problem: For a given class of graphs, what is the maximum k such that there exists a universal point subset of size k? We provide a inverted right perpendicualr root n inverted left perpendicualr lower bound on k for the class of planar graphs with n vertices. In addition, we consider the value F(n, G) such that every set of F(n, G) points in general position is a universal subset for all graphs with n vertices belonging to the family G, and we establish upper and lower bounds for F(n, G) for different families of planar graphs, including 4-connected planar graphs and nested-triangles graphs.
研究論文（国際会議プロシーディングス）, 英語 - Area Bounds of Rectilinear Polygons Realized by Angle Sequences
Sang Won Bae; Yoshio Okamoto; Chan-Su Shin
ALGORITHMS AND COMPUTATION, ISAAC 2012, SPRINGER-VERLAG BERLIN, 7676巻, 掲載ページ 629-638, 出版日 2012年, 査読付, Given a sequence S of angles at n vertices of a rectilinear polygon, S directly defines (or realizes) a set of rectilinear polygons in the integer grid. Among such realizations, we consider the one P(S) with minimum area. Let delta(n) be the minimum of the area of P(S) over all angle sequences S of length n, and Delta(n) be the maximum. In this paper, we provide the explicit formula for delta(n) and Delta(n).
研究論文（国際会議プロシーディングス）, 英語 - The t-pebbling number is eventually linear in t
Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp Zumstein
ELECTRONIC JOURNAL OF COMBINATORICS, ELECTRONIC JOURNAL OF COMBINATORICS, 18巻, 1号, 出版日 2011年07月, 査読付, In graph pebbling games, one considers a distribution of pebbles on the vertices of a graph, and a pebbling move consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The t-pebbling number pi(t)(G) of a graph G is the smallest m such that for every initial distribution of m pebbles on V (G) and every target vertex x there exists a sequence of pebbling moves leading to a distibution with at least t pebbles at x. Answering a question of Sieben, we show that for every graph G, pi(t)(G) is eventually linear in t; that is, there are numbers a, b, t(0) such that pi(t)(G) = at vertical bar b for all t >= t(0). Our result is also valid for weighted graphs, where every edge e = {u, v} has some integer weight omega(e) >= 2, and a pebbling move from u to v removes omega(e) pebbles at u and adds one pebble to v.
研究論文（学術雑誌）, 英語 - A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
Yoshio Okamoto; Takeaki Uno
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, ELSEVIER SCIENCE BV, 210巻, 1号, 掲載ページ 48-56, 出版日 2011年04月, 査読付, We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems. (C) 2010 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Adaptive Algorithms for Planar Convex Hull Problems
Hee-Kap Ahn; Yoshio Okamoto
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E94D巻, 2号, 掲載ページ 182-189, 出版日 2011年02月, 査読付, We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we generalize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearrangement) problems of arrays, and define the "presortedness" as a distance from the input array to the desired output array. We call an algorithm adaptive if it runs faster when a given input array is closer to the desired output, and furthermore it does not make use of any information of the presortedness. As a case study, we look into the planar convex hull problem for which we discover two natural formulations as permutation problems. An interesting phenomenon that we prove is that for one formulation the problem can be solved adaptively, but for the other formulation no adaptive algorithm can be better than an optimal output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a kd-tree.
研究論文（学術雑誌）, 英語 - Hardness results and an exact exponential algorithm for the spanning tree congestion problem
Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno
Journal of Graph Algorithms and Applications, 15巻, 6号, 掲載ページ 727-751, 出版日 2011年, 査読付, Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential- time) exact algorithm that runs in O*(2 n) time, where n denotes the number of vertices. Additionally, we present simple combinatorial lem- mas, which yield a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.
研究論文（学術雑誌）, 英語 - Submodular fractional programming for balanced clustering
Yoshinobu Kawahara; Kiyohito Nagano; Yoshio Okamoto
PATTERN RECOGNITION LETTERS, ELSEVIER SCIENCE BV, 32巻, 2号, 掲載ページ 235-243, 出版日 2011年01月, 査読付, We address the balanced clustering problem where cluster sizes are regularized with submodular functions The objective function for balanced clustering is a submodular fractional function i e the ratio of two submodular functions and thus includes the well-known ratio cuts as special cases In this paper we present a novel algorithm for minimizing this objective function (submodular fractional programming) using recent submodular optimization techniques The main idea is to utilize an algorithm to minimize the difference of two submodular functions combined with the discrete Newton method Thus it can be applied to the objective function involving any submodular functions in both the numerator and the denominator which enables us to design flexible clustering setups We also give theoretical analysis on the algorithm and evaluate the performance through comparative experiments with conventional algorithms by artificial and real datasets (C) 2010 Elsevier B V All rights reserved
研究論文（学術雑誌）, 英語 - Approximability of the Path-Distance-Width for AT-free Graphs
Yota Otachi; Toshiki Saitoh; Katsuhisa Yamanaka; Shuji Kijima; Yoshio Okamoto; Hirotaka Ono; Yushi Uno; Koichi Yamazaki
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 6986巻, 掲載ページ 271-+, 出版日 2011年, 査読付, The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs.
研究論文（国際会議プロシーディングス）, 英語 - Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, SPRINGER-VERLAG BERLIN, 6648巻, 掲載ページ 452-462, 出版日 2011年, 査読付, Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential-time) exact algorithm that runs in O*(2(n)) time, where n denotes the number of vertices. Additionally, we provide a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.
研究論文（国際会議プロシーディングス）, 英語 - Improved Bounds for Wireless Localization
Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
ALGORITHMICA, SPRINGER, 57巻, 3号, 掲載ページ 499-516, 出版日 2010年07月, 査読付, We consider a novel class of art gallery problems inspired by wireless localization that has recently been introduced by Eppstein, Goodrich, and Sitchinava. Given a simple polygon P, place and orient guards each of which broadcasts a unique key within a fixed angular range. In contrast to the classical art gallery setting, broadcasts are not blocked by the edges of P. At any point in the plane one must be able to tell whether or not one is located inside P only by looking at the set of keys received. In other words, the interior of the polygon must be described by a monotone Boolean formula composed from the keys. We improve both upper and lower bounds for the general problem where guards may be placed anywhere by showing that the maximum number of guards to describe any simple polygon on n vertices is between roughly 3/5 n and 4/5 n. A guarding that uses at most 4/5 n guards can be obtained in O(n log n) time. For the natural setting where guards may be placed aligned to one edge or two consecutive edges of P only, we prove that n - 2 guards are always sufficient and sometimes necessary.
研究論文（学術雑誌）, 英語 - On listing, sampling, and counting the chordal graphs with edge constraints
Shuji Kijima; Masashi Kiyomi; Yoshio Okamoto; Takeaki Uno
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 411巻, 26-28号, 掲載ページ 2591-2601, 出版日 2010年06月, 査読付, We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume that at least one of the input graphs is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that indicate that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms' theory to problems arising from various areas such as statistics, data mining, and numerical computation. (C) 2010 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - 支配集合数え上げ問題とグラフクラス
来嶋 秀治; 岡本 吉央; 宇野 毅明
電子情報通信学会コンピュテーション研究会, 掲載ページ 9-15, 出版日 2010年04月
研究論文（研究会，シンポジウム資料等）, 英語 - A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
Ondrej Bilka; Kevin Buchin; Radoslav Fulek; Masashi Kiyomi; Yoshio Okamoto; Shin-ichi Tanigawa; Csaba D. Toth
The Electronic Journal of Combinatorics, 17巻, 出版日 2010年, 査読付
研究論文（学術雑誌）, 英語 - The Geodesic Diameter of Polygonal Domains
Sang Won Bae; Matias Korman; Yoshio Okamoto
ALGORITHMS-ESA 2010, SPRINGER-VERLAG BERLIN, 6346巻, 掲載ページ 500-+, 出版日 2010年, 査読付, This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), it is known that the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithm that computes the geodesic diameter of a given polygonal domain in worst-case time O(n(7.73)) or O(n(7)(log n+h)). Among other results, we show the following geometric observation: the geodesic diameter can be determined by two points in its interior. In such a case, there are at least five shortest paths between the points.
研究論文（国際会議プロシーディングス）, 英語 - Adaptive Algorithms for Planar Convex Hull Problems
Hee-Kap Ahn; Yoshio Okamoto
FRONTIERS IN ALGORITHMICS, SPRINGER-VERLAG BERLIN, 6213巻, 掲載ページ 316-+, 出版日 2010年, 査読付, We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we generalize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearrangement) problems of arrays, and define the "presortedness" as a distance from the input array to the desired output array. We call an algorithm adaptive if it runs faster when a given input array is closer to the desired output, and furthermore it does not make use of any information of the presortedness. As a case study, we look into the planar convex hull problem for which we discover two natural formulations as permutation problems. An interesting phenomenon that we prove is that for one formulation the problem can be solved adaptively, but for the other formulation no adaptive algorithm can be better than an optimal output-sensitive algorithm for the planar convex hull problem.
研究論文（国際会議プロシーディングス）, 英語 - Minimum and Maximum against k Lies
Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp Zumstein
ALGORITHM THEORY - SWAT 2010, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 6139巻, 掲載ページ 139-+, 出版日 2010年, 査読付, A neat 1972 result of Pohl asserts that [3n/2] 2 comparisons are sufficient, and also necessary in the worst case, for finding both the minimum and the maximum of an n-element totally ordered set. The set is accessed via an oracle for pairwise comparisons. More recently, the problem has been studied in the context of the Renyi-Ulam liar games, where the oracle may give up to k false answers. For large k, an upper bound due to Aigner shows that (k + O(root k))n, comparisons suffice. We improve on this by providing an algorithm with at most (k + 1 + C)n,+ O(k(3)) comparisons for some constant C. The known lower bounds are of the form (k + 1 + c(k))n - D, for some constant D, where c(0) = 0.5, c(1) = 23/32 = 0.71875, and c(k) = Omega(2(-5k/4)) as k -> infinity.
研究論文（国際会議プロシーディングス）, 英語 - Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 5911巻, 掲載ページ 296-+, 出版日 2010年, 査読付, We provide polynomial-time algorithms for counting the number of perfect matchings in chain graphs, cochain graphs, and threshold graphs. These algorithms are based on newly developed subdivision schemes that we call a recursive decomposition. On the other hand, we show the #P-completeness for counting the number of perfect matchings in chordal graphs, split graphs and chordal bipartite graphs. Tins is in an interesting contrast with the fact that counting the number of independent sets in chordal graphs can be done in linear time.
研究論文（国際会議プロシーディングス）, 英語 - Untangling a Planar Graph
Xavier Goaoc; Jan Kratochvil; Yoshio Okamoto; Chan-Su Shin; Andreas Spillner; Alexander Wolff
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, 42巻, 4号, 掲載ページ 542-569, 出版日 2009年12月, 査読付, A straight-line drawing delta of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift(G, delta) denote the minimum number of vertices that need to be moved to untangle d. We show that shift(G, delta) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BENDPOINTSETEMBEDDABILITY, a well-known graph-drawing problem.
Further we define fix(G, delta) = n - shift(G, delta) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling d. We give an algorithm that fixes at least root((log n) - 1)/log log n vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least root n/2 vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing delta(G) of G with fix(G, delta(G)) <= root n - 2 + 1 and an n-vertex outerplanar graph H and a drawing delta(H) of H with fix(H, delta(H)) <= 2 root n - 1 + 1. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.
研究論文（学術雑誌）, 英語 - The Holt-Klee condition for oriented matroids
Komei Fukuda; Sonoko Moriyama; Yoshio Okamoto
EUROPEAN JOURNAL OF COMBINATORICS, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 30巻, 8号, 掲載ページ 1854-1867, 出版日 2009年11月, 査読付, Holt and Klee have recently shown that every (generic) LP orientation of the graph of a d-polytope satisfies a directed version of the d-connectivity property, i.e. there are d internally disjoint directed paths from a unique source to a unique sink. We introduce two new classes HK and HK* of oriented matroids (OMs) by enforcing this property and its dual interpretation in terms of line shellings, respectively. Both classes contain all representable OMs by the Holt-Klee theorem. While we give a construction of an infinite family of non-HK* OMs, it is not clear whether there exists any non-HK OM. This leads to a fundamental question as to whether the Holt-Klee theorem can be proven combinatorially by using the OM axioms only. Finally, we give the complete classification of OM(4, 8), the OMs of rank 4 on 8-element ground set with respect to the HK, HK*, Euclidean and Shannon properties. Our classification shows that there exists no non-HK OM in this class. (C) 2008 Elsevier Ltd. All rights reserved.
研究論文（学術雑誌）, 英語 - 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno
電子情報通信学会コンピュテーション研究会, 109号, 掲載ページ 45-52, 出版日 2009年06月
研究論文（研究会，シンポジウム資料等）, 英語 - FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
Heidi Gebauer; Yoshio Okamoto
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, WORLD SCIENTIFIC PUBL CO PTE LTD, 20巻, 1号, 掲載ページ 25-44, 出版日 2009年02月, 査読付, We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O*(1.8494(m)) time for 3-regular graphs, and O*(1.9706(m)) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.
研究論文（学術雑誌）, 英語 - Querying Two Boundary Points for Shortest Paths in a Polygonal Domain (Extended Abstract)
Sang Won Bae; Yoshio Okamoto
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5878巻, 掲載ページ 1054-+, 出版日 2009年, 査読付, We consider a variant of two-point Euclidean shortest path query problem: given a polygonal domain, build a data structure for two-point shortest path query, provided that query points always lie on the boundary of the domain. As a main result, we show that a logarithmic-time query for shortest paths between boundary points can be performed using (O) over tilde (n(5)) preprocessing time and (O) over tilde (n(5)) space where n is the number of corners of the polygonal domain and the (O) over tilde -notation suppresses the polylogarithmic factor. This is realized by observing a connection between Davenport-Schinzel sequences and our problem in the parameterized space. We also provide a tradeoff between space and query time; a sublinear time query is possible using O(n(3+epsilon)) space. Our approach also extends to the case where query points should lie on a given set of line segments.
研究論文（国際会議プロシーディングス）, 英語 - Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability
Kevin Buchin; Maike Buchin; Jaroslaw Byrka; Martin Noellenburg; Yoshio Okamoto; Rodrigo I. Silveira; Alexander Wolff
GRAPH DRAWING, SPRINGER-VERLAG BERLIN, 5417巻, 掲載ページ 324-+, 出版日 2009年, 査読付, A binary tanglegram is a pair < S,T > of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for general binary trees. We show that the problem is hard even if both trees are complete binary trees. For this case we give an O(n(3))-time 2-approximation and a new and simple fixed-parameter algorithm. We show that the maximization version of the dual problem for general binary trees can be reduced to a version of MAXCUT for which the algorithm of Goemans and Williamson yields a 0.878-approximation.
研究論文（国際会議プロシーディングス）, 英語 - Local topology of the free complex of a two-dimensional generalized convex shelling
Yoshio Okamoto
DISCRETE MATHEMATICS, ELSEVIER SCIENCE BV, 308巻, 17号, 掲載ページ 3836-3846, 出版日 2008年09月, 査読付, A generalized convex shelling was introduced by Kashiwabara et al. for their representation theorem of convex geometries. Motivated by the work by Edelman and Reiner, we study local topology of the free complex of a two-dimensional separable generalized convex shelling. As a result, we prove a deletion of an element from such a complex is homotopy equivalent to a single point or two distinct points, depending on the dependency of the element to be deleted. Our result resolves an open problem by Edelman and Reiner for this case, and it can be seen as a first step toward the complete resolution from the viewpoint of a representation theorem for convex geometries by Kashiwabara et al. (C) 2007 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Fair cost allocations under conflicts - a game-theoretic point of view
Yoshio Okamoto
DISCRETE OPTIMIZATION, ELSEVIER SCIENCE BV, 5巻, 1号, 掲載ページ 1-18, 出版日 2008年02月, 査読付, Optimization theory resolves problems to minimize total costs when the agents are involved in some conflicts. In this paper, we consider how to allocate the minimized total cost among the agents. To do that, the allocation is required to be fair in a certain sense. We use a game-theoretic point of view, and provide algorithms to compute fair allocations in polynomial time for a certain conflict situation. More specifically, we study a minimum coloring game, introduced by Deng, Ibaraki and Nagamochi [X. Deng, T. Ibaraki, H. Nagamochi, Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res. 24 (1999) 751-766], and investigate the core, the nucleolus, the tau-value, and the Shapley value. In particular, we provide the following four results. (I) The characterization of the core for a perfect graph in terms of its extreme points. This leads to polynomial-time algorithms to compute a vector in the core, and to determine whether a given vector belongs to the core. (2) A characterization of the nucleolus for some classes of the graphs, including the complete multipartite graphs and the chordal graphs. This leads to a polynomial-time algorithm to compute the nucleolus for these classes of graphs. (3) A polynomial-time algorithm to compute the tau-value for a perfect graph. (4) A polynomial-time algorithm to compute the Shapley value for a forest. The investigation of this paper gives several insights to the relationship of algorithm theory with cooperative games. (C) 2007 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - コーダルサンドイッチの列挙, ランダム生成, 数え上げについて
来嶋 秀治; 清見 礼; 岡本 吉央
数理解析研究所講究録 理論計算機科学の深化 : 新たな計算世界観を求めて, 1599巻, 掲載ページ 148-153, 出版日 2008年
研究論文（研究会，シンポジウム資料等）, 英語 - Counting the number of independent sets in chordal graphs
Yoshio Okamoto; Takeaki Uno; Ryuhei Uehara
Journal of Discrete Algorithms, Elsevier, 6巻, 2号, 掲載ページ 229-242, 出版日 2008年, 査読付, We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant amortized time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.
研究論文（学術雑誌）, 英語 - Improved bounds for wireless localization
Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
ALGORITHM THEORY - SWAT 2008, SPRINGER-VERLAG BERLIN, 5124巻, 掲載ページ 77-+, 出版日 2008年, 査読付, We consider a novel class of art gallery problems inspired by wireless localization. Given a simple polygon P, place and orient guards each of which broadcasts a unique key within a fixed angular range. Broadcasts are not blocked by the edges of P. The interior of the polygon must be described by a monotone Boolean formula composed from the keys. We improve both upper and lower bounds for the general setting by showing that the maximum number of guards to describe any simple polygon on n vertices is between roughly 3/5n and 4/5n. For the natural setting where guards may be placed aligned to one edge or two consecutive edges of P only, we prove that n - 2 guards are always sufficient and sometimes necessary.
研究論文（国際会議プロシーディングス）, 英語 - On listing, sampling, and counting the chordal graphs with edge constraints
Shuji Kijima; Masashi Kiyomi; Yoshio Okamoto; Takeaki Uno
COMPUTING AND COMBINATORICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5092巻, 掲載ページ 458-+, 出版日 2008年, 査読付, We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume at least one of the input pair is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that seem to imply that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms theory to problems arising from various areas such as statistics, data mining, and numerical computation.
研究論文（国際会議プロシーディングス）, 英語 - Moving vertices to make drawings plane
Xavier Goaoc; Jan Kratochvil; Yoshio Okamoto; Chan-Su Shin; Alexander Wolff
GRAPH DRAWING, SPRINGER-VERLAG BERLIN, 4875巻, 掲載ページ 101-+, 出版日 2008年, 査読付, In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In this paper we investigate the related problem MINMOVED VERTICES which asks for the minimum number of vertex moves. First, we show that MINMOVED-VERTICES is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BENDPOINTSETEMBED-DABILITY, which yields similar results for that problem. Third, we give bounds for the behavior of MINMOVED VERTICES on trees and general planar graphs.
研究論文（国際会議プロシーディングス）, 英語 - Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
Yota Otachi; Yoshio Okamoto; Koichi Yamazaki
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 155巻, 17号, 掲載ページ 2383-2390, 出版日 2007年10月, 査読付, We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P-6-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable. (C) 2007 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Matroid representation of clique complexes
Kenji Kashiwabara; Yoshio Okamoto; Takeaki Uno
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 155巻, 15号, 掲載ページ 1910-1929, 出版日 2007年09月, 査読付, In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of "how complex a graph is with respect to the maximum weighted clique problem" since a greedy algorithm is a k-approximation algorithm for this problem. For any k > 0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n - 1. Other related investigations are also given. (c) 2007 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
Yoshio Okamoto; Takeaki Uno
ALGORITHMS AND COMPUTATION, SPRINGER-VERLAG BERLIN, 4835巻, 掲載ページ 609-+, 出版日 2007年, 査読付, We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis & Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems.
研究論文（国際会議プロシーディングス）, 英語 - Fast exponential-time algorithms for the forest counting in graph classes
Heidi Gebauer; Yoshio Okamoto
Proceedings of 13th Computing: The Australasian Theory Symposium (CATS 2007), Australian Computer Society, 掲載ページ 63-69, 出版日 2007年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - The even outdegree conjecture for acyclic PLCP-cubes in dimension five
Sonoko Moriyama; Yoshio Okamoto
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E89D巻, 8号, 掲載ページ 2402-2404, 出版日 2006年08月, 査読付, The behavior of Bard-type pivoting algorithms for the linear complementarity problem with a P-matrix is represented by an orientation of a hypercube. We call it a PLCP-cube. In 1978, Stickney and Watson conjectured that such an orientation has no facet on which all even outdegree vertices appear. We prove that this conjecture is true for acyclic PLCP-cubes in dimension five.
研究論文（学術雑誌）, 英語 - The minimum weight triangulation problem with few inner points
M Hoffmann; Y Okamoto
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, ELSEVIER SCIENCE BV, 34巻, 3号, 掲載ページ 149-158, 出版日 2006年07月, 査読付, We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem, can be solved in O(n(3)) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6(k) n(5) log n) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k = O(log n). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points. (C) 2006 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Core stability of minimum coloring games
Thomas Bietenhader; Yoshio Okamoto
MATHEMATICS OF OPERATIONS RESEARCH, INFORMS, 31巻, 2号, 掲載ページ 418-431, 出版日 2006年05月, 査読付, In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng et al. [10], which arise from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the problem on the core largeness, the extendability, and the exactness of minimum coloring games. As a consequence, we show that it is coNP-complete to decide whether a given game has a large core, is extendable, or is exact.
研究論文（学術雑誌）, 英語 - 多目的最適化問題への列挙アルゴリズム理論からのアプローチ
岡本 吉央; 宇野 毅明
研究集会「最適化：モデリングとアルゴリズム」共同レポート, 掲載ページ 15-25, 出版日 2006年03月, 招待
研究論文（研究会，シンポジウム資料等）, 日本語 - The traveling salesman problem with few inner points
VG Deineko; M Hoffmann; Y Okamoto; GJ Woeginger
OPERATIONS RESEARCH LETTERS, ELSEVIER SCIENCE BV, 34巻, 1号, 掲載ページ 106-110, 出版日 2006年01月, 査読付, We propose two algorithms for the planar Euclidean traveling salesman problem. The first runs in O(k!kn) time and O(k) space, and the second runs in O(2(k)k(2)n) time and O(2(k)kn) space, where n denotes the number of input points and k denotes the number of points interior to the convex hull. (c) 2005 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - The affine representation theorem for abstract convex geometries
K Kashiwabara; M Nakamura; Y Okamoto
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, ELSEVIER SCIENCE BV, 30巻, 2号, 掲載ページ 129-144, 出版日 2005年02月, 査読付, A convex geometry is a combinatorial abstract model introduced by Edelman and Jamison which captures a combinatorial essence of "convexity" shared by some objects including finite point sets, partially ordered sets, trees, rooted graphs. In this paper, we introduce a generalized convex shelling, and show that every convex geometry can be represented as a generalized convex shelling. This is "the representation theorem for convex geometries" analogous to "the representation theorem for oriented matroids" by Folkman and Lawrence. An important feature is that our representation theorem is affine-geometric while that for oriented matroids is topological. Thus our representation theorem indicates the intrinsic simplicity of convex geometries, and opens a new research direction in the theory of convex geometries. (C) 2004 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Linear-time counting algorithms for independent sets in chordal graphs
Y Okamoto; T Uno; R Uehara
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 3787巻, 掲載ページ 433-444, 出版日 2005年, 査読付, We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant amortized time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.
研究論文（学術雑誌）, 英語 - Counting the Independent Sets of a Chordal Graph
岡本 吉央; 宇野 毅明; 上原 隆平
第96回情報処理学会アルゴリズム研究会, 掲載ページ 17-24, 出版日 2004年07月
研究論文（研究会，シンポジウム資料等）, 英語 - Traveling salesman games with the Monge property
Y Okamoto
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 138巻, 3号, 掲載ページ 349-369, 出版日 2004年04月, 査読付, Several works have indicated the relationships between polynomially solvable combinatorial optimization problems and the core non-emptiness of cooperative games associated with them, and between intractable combinatorial optimization problems and the hardness of the problem to decide the core non-emptiness of the associated games. In this paper, we study the core of a traveling salesman game, which is associated with the traveling salesman problem. First, we show that in general the problem to test the core non-emptiness of a given traveling salesman game is N P-hard. This corresponds to the N P-hardness of the traveling salesman problem. Second, we show that the core of a traveling salesman game is non-empty if the distance matrix is a symmetric Monge matrix, and also that a traveling salesman game is submodular (or concave) if the distance matrix is a Kalmanson matrix. These correspond to the fact that the Monge property and the Kalmanson property are polynomially solvable special cases of the traveling salesman problem. (C) 2003 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Core stability of minimum coloring games
T Bietenhader; Y Okamoto
GRAPH -THEORETIC CONCEPTS IN COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 3353巻, 掲載ページ 389-401, 出版日 2004年, 査読付, In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng, Ibaraki & Nagamochi, which arises from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the problem on the core largeness, the extendability, and the exactness of minimum coloring games.
研究論文（学術雑誌）, 英語 - The minimum weight triangulation problem with few inner points
M Hoffmann; Y Okamoto
PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 3162巻, 掲載ページ 200-212, 出版日 2004年, 査読付, We propose to look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem can be solved in O(n(3)) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6(k)n(5) log n) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k = O(log n). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k interior points.
研究論文（学術雑誌）, 英語 - The traveling salesman problem with few inner points
VG Deineko; M Hoffmann; Y Okamoto; GJ Woeginger
COMPUTING AND COMBINATORICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 3106巻, 掲載ページ 268-277, 出版日 2004年, 査読付, We study the traveling salesman problem (TSP) in the 2-dimensional Euclidean plane. The problem is NP-hard in general, but trivial if the points are in convex position. In this paper, we investigate the influence of the number of inner points (i.e., points in the interior of the convex hull) on the computational complexity of the problem. We give two simple algorithms for this problem. The first one runs in 0(k!kn) time and O(k) space, and the second runs in 0(2(k)k(2)n) time and 0(2(k)kn) space, when n is the total number of input points and k is the number of inner points. Hence, if k is taken as a parameter, this problem is fixed-parameter tractable (FPT), and also can be solved in polynomial time if k = 0 (log n). We also consider variants of the TSP such as the prize-collecting TSP and the partial TSP in this setting, and show that they are FPT as well.
研究論文（学術雑誌）, 英語 - Submodularity of some classes of the combinatorial optimization games
Y Okamoto
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, SPRINGER HEIDELBERG, 58巻, 1号, 掲載ページ 131-139, 出版日 2003年10月, 査読付, Submodularity (or concavity) is considered as an important property in the field of cooperative game theory. In this article, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game on a given graph is submodular or not. Related to these results, the Shapley values are also investigated.
研究論文（学術雑誌）, 英語 - The forbidden minor characterization of line-search antimatroids of rooted digraphs
Y Okamoto; M Nakamura
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 131巻, 2号, 掲載ページ 523-533, 出版日 2003年09月, 査読付, An antimatroid is an accessible Union-closed family of subsets of a finite set. A number of classes of antimatroids are closed under taking minors such as point-search antimatroids of rooted (di)graphs, line-search antimatroids of rooted (di)graphs, shelling antimatroids of rooted trees, shelling antimatroids of posets, etc. The forbidden minor characterizations are known for point-search antimatroids of rooted (di)graphs, shelling antimatroids of rooted trees and shelling antimatroids of posets. In this paper, we give the forbidden minor characterization of line-search antimatroids of rooted digraphs. (C) 2002 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - A greedy algorithm for convex geometries
K Kashiwabara; Y Okamoto
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 131巻, 2号, 掲載ページ 449-465, 出版日 2003年09月, 査読付, Convex geometries are closure spaces which satisfy anti-exchange property, and they are known as dual of antimatroids. We consider functions defined on the sets of the extreme points of a convex geometry. Faigle-Kern (Math. Programming 72 (1996) 195-206) presented a greedy algorithm to linear programming problems for shellings of posets, and Kruger (Discrete Appl. Math. 99 (2002) 125-148) introduced b-submodular functions and proved that Faigle-Kern's algorithm works for shellings of posets if and only if the given set function is b-submodular. We extend their results to all classes of convex geometries, that is, we prove that the same algorithm works for all convex geometries if and only if the given set function on the extreme sets is submodular in our sense. (C) 2003 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Fair cost allocations under conflicts - A game-theoretic point of view
Y Okamoto
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 2906巻, 掲載ページ 686-695, 出版日 2003年, 査読付, We study the cost allocation problem when the players are involved in a conflict situation. More formally, we consider a minimum coloring game, introduced by Deng, Ibaraki & Nagamochi, and provide algorithms for the core, the tau-value, the nucleolus and the Shapley value on some classes of graphs. The investigation gives several insights to the relationship of algorithm theory with cooperative games.
研究論文（学術雑誌）, 英語 - Greedy edge-disjoint paths in complete graphs
P Carmi; T Erlebach; Y Okamoto
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 2880巻, 掲載ページ 143-155, 出版日 2003年, 査読付, The maximum edge-disjoint paths problem (MEDP) is one of the most classical NP-hard problems. We study the approximation ratio of a simple and practical approximation algorithm, the shortest-path-first greedy algorithm (SCA), for MEDP in complete graphs. Previously, it was known that this ratio is at most 54. Adapting results by Kolman and Scheideler [Proceedings of SODA, 2002, pp. 184-193], we show that SGA achieves approximation ratio 8F + 1 for MEDP in undirected graphs with flow number F and, therefore, has approximation ratio at most 9 in complete graphs. Furthermore, we construct a family of instances that shows that SGA cannot be better than a 3-approximation algorithm. Our upper and lower bounds hold also for the bounded-length greedy algorithm, a simple on-line algorithm for MEDP.
研究論文（学術雑誌）, 英語 - The free complex of a two-dimensional generalized convex shelling
Yoshio Okamoto
EUROCOMB'03 -- Abstracts, 掲載ページ 289-293, 出版日 2003年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Matroid representation of clique complexes
K Kashiwabara; Y Okamoto; T Uno
COMPUTING AND COMBINATORICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 2697巻, 掲載ページ 192-201, 出版日 2003年, 査読付, In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of "how complex a graph is with respect to the maximum weighted clique problem" since a greedy algorithm is a k-approximation algorithm for this problem. We characterize graphs whose-clique complexes can be represented as the intersection of k matroids for any k > 0. Moreover, we determine the necessary and sufficient number of matroids for. the representation of all graphs with n vertices. This number turns out to be n - 1. Other related investigations are also given.
研究論文（学術雑誌）, 英語 - Some properties of the core on convex geometries
Yoshio Okamoto
Mathematical Methods of Operations Research, 56巻, 掲載ページ 377-386, 出版日 2002年, 査読付
研究論文（学術雑誌）, 英語
MISC
- ネットワーク型交渉ゲームの安定化アルゴリズム
伊藤健洋; 垣村尚徳; 神山直之; 小林佑輔; 岡本吉央
出版日 2016年02月28日, 情報処理学会研究報告(Web), 2016巻, AL-157号, 掲載ページ VOL.2016‐AL‐157,NO.3 (WEB ONLY), 日本語, 201602218370461602 - 1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))
伊藤 健洋; 垣村 尚徳; 神山 直之; 小林 佑輔; 岡本 吉央
公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2015年03月26日, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015巻, 掲載ページ 44-45, 日本語, 110009981367 - Minimum-Cost b-Edge Dominating Sets on Trees
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP.We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP., 一般社団法人情報処理学会, 出版日 2015年02月24日, 研究報告アルゴリズム（AL）, 2015巻, 2号, 掲載ページ 1-6, 英語, 0919-6072, 110009877668, AN1009593X - 境界上の重みの釣合せ (計算理論とアルゴリズムの新潮流)
バルバ ルイス; 鄭 地園; カルフェル ジャン・ルー・ド; ドビンズ マイケル; フライシャー ルードルフ; 河村 彰星; コルマン マティアス; 岡本 吉央; パハ ヤーノシュ; 唐 淵; 徳山 豪; バードンスホト サンダー; 王 天豪
京都大学, 出版日 2014年05月, 数理解析研究所講究録, 1894巻, 掲載ページ 45-52, 日本語, 1880-2818, 110009804829, AN00061013 - Guest editorial: Selected papers from ISAAC 2011
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
出版日 2013年09月, Algorithmica, 67巻, 1号, 掲載ページ 1-2, 英語, 0178-4617, 84879268935 - Computational complexity and an integer programming model of Shakashaka (コンピュテーション)
ドメイン エリック・D; 岡本 吉央; 上原 隆平; 宇野 裕之
パズル「シャカシャカ」は,有名な数独をはじめとする多くのペンシルパズルと同様,日本の出版社ニコリが普及させたパズルである.これまで「シャカシャカ」の計算複雑さは未解決であった.本稿ではまず「シャカシャカ」がNP完全であることを示す.次に「シャカシャカ」を整数計画問題として記述する.これを実装し,市販されている本の問題をIPソルバで解いた実験結果を示す.その結果,どの問題も1秒以内に解けた., 一般社団法人電子情報通信学会, 出版日 2013年04月24日, 電子情報通信学会技術研究報告 : 信学技報, 113巻, 14号, 掲載ページ 43-48, 英語, 0913-5685, 110009768472, AN10013152 - GUEST EDITORS' FOREWORD
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
WORLD SCIENTIFIC PUBL CO PTE LTD, 出版日 2013年04月, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 23巻, 2号, 掲載ページ 73-74, 英語, その他, 0218-1959, 1793-6357, WOS:000327447000001 - グラフを通したパズル・ゲームの一般化
岡本 吉央
パズルやゲームの中には登場するモノの間の相互関係が重要になるものが多い.例えば,本特集における伊藤大雄氏の記事ではジャンケンにおける各手の関係を有向グラフとして見ることにより,その一般化を考察している.本稿ではほかの例として「アルクインの川渡りパズル」と「帽子パズル」を考察対象とする.この2つについては近年研究が進んでおり,そのなかで未解決である問題についても言及する., 公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2013年03月01日, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 58巻, 3号, 掲載ページ 161-166, 日本語, 0030-3674, 110009594408, AN00364999 - 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について
並河 雄紀; 岡本 吉央; 大舘 陽太
施設配置ゲームは施設配置問題から生じる協力ゲームである．この問題では，施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし，最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える．しかし，実際にそのような解を計算しようとすると，計算量理論の意味で難しいことが多い．本稿では，施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する．具体的には，施設の数が2個かつ費用が2種類に制限された場合に，凸ゲームと呼ばれる良い性質を持つクラスに属するための必要十分条件を示す．さらに，施設が2個かつ費用が2種類の場合にはシャープレイ値が顧客数の多項式時間計算可能であることを示す．We study facility location games, which arise from the facility location problem as a cooperative game. In this game, customers in the facility location problem minimize their cost through cooperation, and the minimized cost is distributed among the customers by a solution concept from cooperative game theory. However, computation of such a solution can be hard in the sense of computational complexity theory. We concentrate on an uncapacitated facility location game. When there are at most two facilities, and the cost is restricted to two values, we characterize a convex game, which has several nice properties. Furthermore, when there are at most two facilities, and the cost is restricted to two values, we show that the Shapley value can be computed in polynomial time in the size of customers., 出版日 2013年02月22日, 研究報告アルゴリズム（AL）, 2013巻, 3号, 掲載ページ 1-8, 日本語, 110009550136, AN1009593X - 『計算機科学者のためのゲーム理論入門』シリーズ第4回 : メカニズムデザイン(応用編)
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
本稿では，メカニズムデザイン(応用編)として，前回の基礎編に対して，現実からの要請にもとづく社会的に望ましい結果，もしくは設計者の目的を満たす結果，をもたらすための市場や制度をメカニズムとしてどう考えるかに焦点をあてる．まず，メカニズムデザイン理論における代表的な応用である，異なる種類の商品を同時に販売するためのオークション，いわゆる組合せオークションを，もっともよく知られているVickrey-Clarke-Grovesメカニズムを通して説明する．次に，従来は考えられていなかった課題を解決するためのメカニズムをどのように設計するかを解説するために，架空名義入札を取り上げる．加えて，メカニズムデザイン理論のよく知られた実践例である，検索連動型広告オークションとマッチングメカニズムの主要な結果に関して述べる．, 日本ソフトウェア科学会, 出版日 2013年01月25日, コンピュータソフトウェア, 30巻, 1号, 掲載ページ 34-52, 日本語, 0289-6540, 10031138249 - 協力ゲーム
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
This tutorial introduces a cooperative game theory which is one of main parts in game theory. A cooperative game theory consists of two major research topics. The first topic involves how to divide the value of the coalition among agents. We explain the desirable ways of dividing the rewards among cooperative agents, called solution concepts. The traditional cooperative game theory provides a number of solution concepts, such as the core, the Shapley value, and the nucleolus. We introduce some algorithms for dividing the obtained rewards among agents and show their computational complexities. The second topic involves partitioning a set of agents into coalitions so that the sum of the rewards of all coalitions is maximized. This is called Coalition Structure Generation problem (CSG). We explain efficient constraint optimization algorithms for solving the CSG problem. Furthermore, we introduce concise representation schemes for a characteristic function, since it is likely that we can solve solution concepts/CSG problem more efficiently by utilizing concise representation methods for a game. © 2013, Japan Society for Software Science and Technology. All rights reserved., 日本ソフトウェア科学会 ; 1984-, 出版日 2013年, コンピュータソフトウェア, 30巻, 2号, 掲載ページ 33-51, 英語, 0289-6540, 10031151473, 84883333397 - 『計算機科学者のためのゲーム理論入門』シリーズ第5回 協力ゲーム
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
本稿では，ゲーム理論の主要領域の1つである協力ゲームについて解説する．協力ゲームは，主に2つの研究領域からなる．1つは，提携内のプレイヤ間で，協力によって得られた利益をどのように分配するかである．本編では，解概念と呼ばれる，協力的なエージェント間で利得を配分する望ましい方法について概説する．古典的な協力ゲーム理論では，コア，シャプレイ値，仁など，さまざまな解概念が提案されている．これらの解概念によって与えられる利得の配分を求めるアルゴリズムと計算量について考察する．2つ目は，全体提携が最適ではない場合，プレイヤがどのような協力関係(提携)を形成するかである．これは，提携構造形成問題(CSG)と呼ばれる．本編では，CSGを効率的に解く制約付き最適化アルゴリズムを紹介する．また，本編ではゲームの簡潔表現法を利用することで解概念やCSGに関する問題を効率的に解くことができるため，協力ゲームの簡潔な記述方法を概説する．, 日本ソフトウェア科学会, 出版日 2013年, コンピュータ ソフトウェア, 30巻, 2号, 掲載ページ 2_33-2_51, 日本語, 0289-6540, 130004892257 - メカニズムデザイン(基礎編)
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
本稿では，メカニズムデザイン(基礎編)として，メカニズムデザイン理論について概説する．メカニズムデザイン理論は不完備情報ゲームの枠組みを用いて，自身の利得の最大化を目指して行動するプレイヤの集団が，あるルール(メカニズム)の元でどのように振る舞うかを分析すると共に，どのようにメカニズムを設計すれば社会的に望ましい結果，もしくは設計者の目的を満たす結果を達成できるかを扱う理論である．本稿では，まずメカニズムデザインの基礎となる不完備情報ゲームを説明する．そして，メカニズムデザインの代表的な適用例であるオークションに即して，メカニズムデザインの考え方，およびただ1つの商品を販売するオークションにおけるメカニズムデザイン理論の主要結果を概説する．, 日本ソフトウェア科学会, 出版日 2012年10月25日, コンピュータソフトウェア, 29巻, 4号, 掲載ページ 15-31, 日本語, 0289-6540, 10031077886 - 施設配置ゲームにおける仁・シャープレイ値の計算について
並河 雄紀; 岡本 吉央; 大舘 陽太
施設配置ゲームは施設配置問題から生じる協力ゲーム的問題である.この問題では,施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし,最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える.しかし,実際にそのような解を計算しようとすると,計算量理論の意味で難しいことが多い.本稿では,施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する.具体的には,施設の数が2個かつ費用が2種類の場合に,凸ゲームと呼ばれる良い性質を持つクラスに属するための必要十分条件を示す.さらに,一般の容量制約なし施設配置ゲームにおいて,仁とシャープレイ値が一致する例を示す., 一般社団法人電子情報通信学会, 出版日 2012年10月24日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 112巻, 272号, 掲載ページ 25-32, 日本語, 0913-5685, 110009636909, AN10013152 - 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
清見 礼; 岡本 吉央; 斎藤 寿樹
不完全なデータが与えられたときに,形質に基づいて系統樹を復元する問題を研究する.より正確には,形質が二値であり,有向完全系統樹の仮定が成り立つ場合に,ある種に対してある形質の状態がデータとして失われている状況を考える.本研究の目的は失われたデータを補完したときに得られる完全系統樹をすべて列挙するための効率的アルゴリズムを設計することである.単純な分枝限定アルゴリズム(B&B)は理論的に良い計算量を持つが,ゼロサプレス型二分決定グラフ(ZDD)に基づく別の方法を提案する.ランダム生成されたデータに対する実験では,ZDDに基づく手法がB&Bよりも優れた結果を示した.また,与えられた不完全データと矛盾しない完全系統樹の数を計算する問題が#P完全であることを示し,すなわち,効率的標本抽出が難しいことの傍証を与える., 一般社団法人電子情報通信学会, 出版日 2012年06月14日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 112巻, 93号, 掲載ページ 17-24, 英語, 0913-5685, 110009588447, AN10013152 - 列挙の基本と基礎的なアルゴリズム
岡本 吉央
列挙問題とは,与えられた条件を満たすものを漏れなく,重複なく出力する問題である.本稿では,列挙問題を解くためのアルゴリズム設計技法として基礎的なものを紹介する.まず,列挙アルゴリズムの効率の良さの測り方を導入する.その後で,部分集合列挙問題を例題として,分割法,グレイコード,逆探索法という三つの設計技法を紹介する.最後に,効率の良い列挙アルゴリズムを設計することが難しい列挙問題とその理由について言及する., 一般社団法人電子情報通信学会, 出版日 2012年06月01日, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, 95巻, 6号, 掲載ページ 477-483, 日本語, 0913-5693, 110009457693, AN1001339X - 『計算機科学者のためのゲーム理論入門』シリーズについて
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
日本ソフトウェア科学会, 出版日 2012年04月25日, コンピュータソフトウェア, 29巻, 2号, 掲載ページ 65-68, 日本語, 0289-6540, 10030311272 - 非協力ゲーム(基礎編)
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
本稿では，ゲーム理論の基礎となる標準形の非協力ゲームについて概説する．標準形の非協力ゲームでは，複数のプレイヤが，自身の利得の最大化を目指して，独立かつ同時に行動を選択する．各プレイヤの利得は，自身の行動と他のプレイヤの行動の組合せにより決定される．非協力ゲームの帰結を予測するために，様々な均衡概念が提案されている．本稿では，標準形の非協力ゲームの基礎となる用語と均衡概念について概説する．また，単純に標準形の非協力ゲームを記述した場合，その記述量はプレイヤの数に対して指数的に増加する．本編では，ゲームの簡潔な記述方法であるグラフィカルゲームと混雑ゲーム，およびこれらのゲームにおいて均衡を計算するためのアルゴリズム/計算量について概説する．, 日本ソフトウェア科学会, 出版日 2012年04月25日, コンピュータソフトウェア, 29巻, 2号, 掲載ページ 69-84, 日本語, 0289-6540, 10030311279 - Special Issue: Selected Papers from the 21st Annual International Symposium on Algorithms and Computation FOREWORD
Otfried Cheong; Yoshio Okamoto
WORLD SCIENTIFIC PUBL CO PTE LTD, 出版日 2012年02月, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 22巻, 1号, 掲載ページ 1-2, 英語, その他, 0218-1959, WOS:000308707000001 - 非協力ゲーム(発展編)
横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
本編では非協力ゲーム(発展編)として，非協力ゲームの均衡概念で最も重要なものであるナッシュ均衡について詳しく述べる．2人ゼロサム標準形ゲームでは，プレイヤが選択可能な純粋戦略の個数に関する多項式時間でナッシュ均衡を計算できる．しかしながら，プレイヤが交互に行動を繰り返し選択するような複雑なゲームでは純粋戦略の個数が膨大となる．本編では，このような複雑な2人ゼロサムゲームの均衡を計算する例として，ポーカー等のカードゲームにおいてナッシュ均衡を計算するアルゴリズムを紹介する．一方，一般の有限2人標準形ゲームでは，ナッシュ均衡が多項式時間で計算可能かどうかが分かっていない．しかしながら，ナッシュ均衡の存在自体は証明されているので，PやNPのような判定問題に関する概念は，ナッシュ均衡計算問題の難しさを議論するためには適切ではない．本編では，ナッシュ均衡計算問題の難しさを議論する際に有用な問題のクラスであるPPAD，およびPPAD完全性について解説する．, 日本ソフトウェア科学会, 出版日 2012年, コンピュータ ソフトウェア, 29巻, 3号, 掲載ページ 3_39-3_53, 日本語, 0289-6540, 130004549284 - Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
Okamoto Yoshio; Otachi Yota; Uehara Ryuhei; UNO TAKEAKI
一般社団法人電子情報通信学会, 出版日 2011年08月30日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 111巻, 195号, 掲載ページ 31-38, 英語, 0913-5685, 110008900047, AN10013152 - Approximating the path-distance-width for k-cocomparability graphs
Yota Otachi; Toshiki Saitoh; Katsuhisa Yamanaka; Shuji Kijima; Yoshio Okamoto; Hirotaka Ono; Yushi Uno; Koichi Yamazaki
出版日 2011年02月28日, 研究報告アルゴリズム（AL）, 2011巻, 1号, 掲載ページ 1-8, 英語, 110008583076, AN1009593X - 絵画的迷路の作り方 (理論計算機科学の深化と応用)
岡本 吉央; 上原 隆平
京都大学, 出版日 2009年05月, 数理解析研究所講究録, 1649巻, 掲載ページ 58-65, 日本語, 1880-2818, 110007105293, AN00061013 - 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
岡本 吉央; 宇野 毅明
公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2006年03月14日, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2006巻, 掲載ページ 212-213, 日本語, 110006168732, AN00351206 - 第4回 離散最適化と協力ゲーム(2)
毛利 裕昭; 岡本 吉央
公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2003年02月01日, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 48巻, 2号, 掲載ページ 114-120, 日本語, 0030-3674, 110001183690, AN00364999
書籍等出版物
- 応用数理ハンドブック
岡本吉央
事典・辞書, 日本語, 共著, 離散システム (近似アルゴリズム), 朝倉書店, 出版日 2013年10月25日 - 離散体積計算による組合せ論入門
岡本吉央
日本語, 単訳, シュプリンガー・ジャパン, 出版日 2010年 - 離散数学のすすめ
日本語, 共著, 第3章「平面上の点集合から見た離散数学」, 現代数学社, 出版日 2010年 - Encyclopedia of Algorithms
英語, 共著, Traveling Sales Person with Few Inner Points, Springer, 出版日 2008年 - 離散幾何学講義
岡本吉央
日本語, 単訳, シュプリンガー・フェアラーク東京, 出版日 2005年 - 凸多面体の数学
八森正泰; 岡本吉央
日本語, 共訳, シュプリンガー・フェアラーク東京, 出版日 2003年
担当経験のある科目_授業
- Theory of Computation
The University of Electro-Communications - 計算理論
電気通信大学 - 情報・通信工学基礎
The University of Electro-Communications - 情報・通信工学基礎
電気通信大学 - 情報・通信工学基礎
電気通信大学 - Mathematical Information Science Laboratory IIB
The University of Electro-Communications - Mathematical Information Science Laboratory IIA
The University of Electro-Communications - 離散数学
電気通信大学 - 離散数理工学
電気通信大学 - キャリア教育演習
電気通信大学 - キャリア教育演習
電気通信大学 - Introduction to Science and Technology Studies II
The University of Tokyo - 科学技術社会論II
東京大学 - Discrete Mathematical Engineering
The University of Electro-Communications - 離散数理工学
電気通信大学 - Graphs and Networks
The University of Electro-Communications - グラフとネットワーク
電気通信大学 - 最適化手法
中央大学 - 最適化手法
中央大学 - 数理科学特別講義VIII／数理科学特論8
九州大学 - 数理科学特別講義VIII／数理科学特論8
九州大学 - 情報数理科学特別講義D／情報数理科学特別講義H／情報数理科学特殊講義B
大阪府立大学 - 情報数理科学特別講義D／情報数理科学特別講義H／情報数理科学特殊講義B
大阪府立大学 - Graduate Course of Science and Technology on Communications
The University of Electro-Communications - 大学院総合コミュニケーション科学
電気通信大学 - Information Engineering Laboratory
The University of Electro-Communications - 情報工学工房
電気通信大学 - Graduate Technical English
The University of Electro-Communications - 大学院技術英語
電気通信大学 - Mathematical Information Science Laboratory II A
The University of Electro-Communications - 情報数理工学実験第二A
電気通信大学 - Discrete Mathematics
The University of Electro-Communications - 離散数学
電気通信大学 - Foundation of Discrete Optimization
The University of Electro-Communications - 離散最適化基礎論
電気通信大学 - Mathematical Information Science Laboratory II B
The University of Electro-Communications - 情報数理工学実験第二B
電気通信大学 - Mathematical Analysis
The University of Electro-Communications - 数理解析
電気通信大学
所属学協会
共同研究・競争的資金等の研究課題
- 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合
伊藤 健洋; 川原 純; 岡本 吉央; 鈴木 顕
日本学術振興会, 科学研究費助成事業, 東北大学, 学術変革領域研究(B), 本研究は，研究領域「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」の総括班であり，その目的は「班間連携の促進」と「外部への広報活動」の大きく２つである．これらを実現するために，下記の通り活動を行った． まず，本年度の領域会議を2020年10月30日と2021年3月23日の２回完全オンラインにて開催した．１０月の領域会議では，本研究領域の全体像をメンバーらと再確認した．３月の領域会議では，班間連携を促進するためにも，各計画研究班の半年間の研究動向を報告し合い，研究討論を行った．また，１０月，３月の領域会議ともに，同日に一般公開のシンポジウムも併催した．１０月の公開シンポジウムは，キックオフミーティングと銘打って，本研究領域の目的と計画を中心に解説した．３月の公開シンポジウムでは，招待講演も企画した． さらにオンラインでは，組合せ遷移のセミナー・勉強会を継続して行った．2020年度中には７回開催し，それらは全て一般公開している．セミナー・勉強会は，本研究領域のメンバーが自身の研究を紹介することで，その背景分野を互いに勉強し合い，班間連携の促進につなげることを目的としている． この他にもアウトリーチ活動として，本研究領域Webサイトの開設，ニュースレター創刊号の発行，電気通信大学主催の産学官連携イベントでの発表などを行った． また，大容量メモリ搭載計算サーバを設置し，本研究領域のメンバーが利用できるように環境整備を行った．, 20H05792
研究期間 2020年10月 - 2023年03月 - 数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ
研究代表者
研究期間 2020年10月 - 2023年03月 - 大規模配位空間の最適化理論：離散構造論の視点を中心にして
基盤研究(C)一般, 研究代表者
研究期間 2020年04月 - 2023年03月 - パラメータ化計算量による幾何近似アルゴリズム
JSPS, 二国間事業共同研究 (インド (DST) との共同研究)
研究期間 2019年 - 2021年 - 内在構造に基づく大規模グラフの高速処理とその理論基盤構築
栢森情報科学振興財団, 研究助成
研究期間 2017年01月 - 2018年12月 - 計算幾何学と計算トポロジーが拓く新時代データ解析の理論基盤
基盤研究(C)一般, 研究代表者
研究期間 2015年 - 2017年 - 持続可能な発展のための資源配分メカニズム設計理論の構築
基盤研究(S), 研究分担者
研究期間 2012年 - 2016年 - 最適化技法との融合による計算限界解析法の深化
新学術領域研究（研究課題提案型）, 研究分担者, 新学術領域研究（研究領域提案型）
研究期間 2012年 - 2016年 - 厳密計算における信頼性とその理論保証のための数理的アプローチ
若手研究(B), 研究代表者
研究期間 2012年 - 2014年 - 大規模なセンサネットワーク位置推定問題の数値解法に関する研究
小島 政和; 岡本 吉央; 三好 直人; 山下 真; 藤澤 克樹
日本学術振興会, 科学研究費助成事業, 東京工業大学, 基盤研究(B)一般, 研究分担者, センサネットワークは,環境モニタリング,構造物管理,交通制御などのさまざまな分野で使われている.アンカーと呼ばれるその位置が既知のm個のセンサとネットワーク上で隣接するセンサ間の距離の情報からその位置が未知のn個のセンサの位置を推定する問題は最も基本的で重要な問題の1つである.理論的にはNP困難な難しい問題として知られており,さまざまな分野で研究が行われている.この研究課題では,センサネットワーク位置推定問題に対する半正定値計画緩和を中心に研究を進めた.半正定値計画緩和は精度の良い推定位置を生成することが知られているが,センサネットワーク位置推定問題の規模の増加に伴って,計算コストが急速に増加する欠点を有している.この欠点を解消するためにネットワークの構造的な疎性の有効利用および半正定値計画問題を解く主双対内点法ソフトウェアSDPAの高速化をおこなった.この研究課題の主たる研究成果として大規模な問題を高速に解くソフトウェアパッケージSFSDPを開発・公開した., 22310089
研究期間 2010年 - 2012年 - 多面体的組合せ論に基づく数え上げアルゴリズム設計理論の構築
岡本 吉央
日本学術振興会, 科学研究費助成事業, 若手研究(B), 研究代表者, グラフに対する数え上げ問題,離散幾何・計算幾何に関する数え上げ問題,そして,最適化問題に対するそれらの応用に関して研究成果を得た.例を挙げると,グラフの部分構造である支配集合を数え上げる問題に対して,グラフクラスの観点からその困難性を明らかにした.また,多角形領域における距離関数最大化問題の局所最適解を列挙するアルゴリズムを開発し,そこから大域最適解が多項式時間で見つけられることを示した.これらを査読付き英文論文誌,ならびに,査読付き国際会議にて発表した., 21700009
研究期間 2009年 - 2011年 - グラフ・ネットワーク上のゲーム理論に対するアルゴリズム理論的厳密アプローチ
岡本 吉央
日本学術振興会, 科学研究費助成事業, 若手研究(B), 研究代表者, グラフ・ネットワークに関わる協力ゲーム理論について,アルゴリズム理論・計算理論の観点から精緻な議論を行った.特に,最小彩色ゲームと呼ばれる費用分担問題に対して,今までに提案された公平な費用分担の中のいくつかが効率よく計算できることを示した.それに加えて,コア安定性問題に対する計算量理論的な解析も行った.さらに,最小費用全域木ゲームと呼ばれる費用分担問題に対して,公平費用分担が効率よく計算できるための十分条件である劣モジュラ性を満たす場合の考察をした., 18710130
研究期間 2006年 - 2008年 - 実践的な列挙アルゴリズムの理論構築
宇野 毅明; 中野 眞一; 松井 泰子; 岡本 吉央; 清見 礼
日本学術振興会, 科学研究費助成事業, 国立情報学研究所, 特定領域研究（計画）, 研究分担者, 研究分担者となったのは2004年度から．, 16092227
研究期間 2004年 - 2007年