Yoshio OKAMOTO
| Department of Computer and Network Engineering | Professor |
| Cluster I (Informatics and Computer Engineering) | Professor |
Researcher Information
Research Keyword
Field Of Study
- Informatics, Information theory
- Informatics, Mathematical informatics
- Natural sciences, Basic mathematics
- Natural sciences, Applied mathematics and statistics
- Social infrastructure (civil Engineering, architecture, disaster prevention), Social systems engineering
- Social infrastructure (civil Engineering, architecture, disaster prevention), Safety engineering
Career
- 01 Apr. 2017
電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 教授 - 01 Apr. 2016 - 31 Mar. 2017
電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 准教授 - 01 Apr. 2012 - 31 Mar. 2016
電気通信大学, 大学院情報理工学研究科 情報・通信工学専攻, 准教授 - 01 Oct. 2010 - 31 Mar. 2012
北陸先端科学技術大学院大学, 大学院教育イニシアティブセンター, 特任准教授 - 01 Dec. 2007 - 30 Sep. 2010
東京工業大学, 大学院情報理工学研究科, 特任准教授 - 01 Apr. 2007 - 30 Nov. 2007
豊橋技術科学大学, 工学部 情報工学系, 助教 - 01 Apr. 2005 - 31 Mar. 2007
豊橋技術科学大学, 工学部 情報工学系, 助手
Educational Background
- Apr. 2002 - Mar. 2005
ETH Zurich, Department of Computer Science, Switzerland - Apr. 1999 - Mar. 2001
The University of Tokyo, Graduate School of Arts and Sciences, Department of General Systems Studies - Apr. 1995 - Mar. 1999
The University of Tokyo, College of Arts and Sciences, Department of Systems Science - Apr. 1992 - Mar. 1995
岡崎高等学校, 普通科
Research Activity Information
Award
- Jan. 2024
情報処理学会
2023年度コンピュータサイエンス領域功績賞, 岡本吉央
Japan society - Mar. 2022
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会フェロー - Sep. 2021
船井ベストペーパー賞, 岡本吉央;伊藤健洋;垣村尚徳;神山直之;小林佑輔
Japan society - Sep. 2020
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会第10回研究賞
Japan society - 2015
日本ソフトウェア科学会
日本ソフトウェア科学会第5回解説論文賞, 横尾真;岩崎敦;櫻井祐子;岡本吉央
Japan society - 2012
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会研究賞奨励賞 - 2010
EATCS, LA Symposium
8th EATCS/LA Presentation Award - 2004
Editors' Choice 2003, Discrete Applied Mathematics
Paper
- Minimum separator reconfiguration
Guilherme C.M. Gomes; Clément Legrand-Duchesne; Reem Mahmoud; Amer E. Mouawad; Yoshio Okamoto; Vinicius F. dos Santos; Tom C. van der Zanden
Journal of Computer and System Sciences, Elsevier BV, 146, 103574-103574, Dec. 2024, Peer-reviwed, True, with international co-author(s)
Scientific journal - CoRe Challenge 2022/2023: Empirical Evaluations for Independent Set Reconfiguration Problems (Extended Abstract)
Takehide Soh; Tomoya Tanjo; Yoshio Okamoto; Takehiro Ito
Proceedings of the 17th International Symposium on Combinatorial Search (SOCS 2024), Association for the Advancement of Artificial Intelligence (AAAI), 17, 285-286, 01 Jun. 2024, Peer-reviwed, True
International conference proceedings - 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, Dec. 2023, Peer-reviwed
International conference proceedings - 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, Nov. 2023, Peer-reviwed
Scientific journal - 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, 31 Jan. 2023, Peer-reviwed
Scientific journal - 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, Jan. 2023, Peer-reviwed
Scientific journal - 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, Nov. 2022, Peer-reviwed
In book - 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, Jun. 2022, Peer-reviwed
International conference proceedings, English - 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, Jun. 2022, Peer-reviwed, with international co-author(s)
English - 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, Jun. 2022, Peer-reviwed
Scientific journal - 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, May 2022, Peer-reviwed
Scientific journal - 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, Jan. 2022, Peer-reviwed
International conference proceedings - 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, Feb. 2021, Peer-reviwed
Scientific journal - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
Scientific journal, English - Algorithmic enumeration of surrounding polygons
Katsuhisa Yamanaka; David Avis; Takashi Horiyama; Yoshio Okamoto; Ryuhei Uehara; Tanami Yamauchi
Discrete Applied Mathematics, Elsevier BV, Apr. 2020, Peer-reviwed
Scientific journal - Linear-Time Recognition of Double-Threshold Graphs
Yusuke Kobayashi; Yoshio Okamoto; Yota Otachi; Yushi Uno
Proceedings of 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), Springer, 286-297, 2020, Peer-reviwed
International conference proceedings, English - Subgraph Isomorphism on Graph Classes that Exclude a Substructure.
Hans L. Bodlaender; Tesshu Hanaka; Yoshio Okamoto; Yota Otachi; Tom C. van der Zanden
Algorithms and Complexity - 11th International Conference(CIAC), Springer, 82, 12, 87-98, 2019, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings - Computing the Geodesic Centers of a Polygonal Domain
Sang Won Bae; Matias Korman; Yoshio Okamoto
Computational Geometry: Theory and Applications, 77, 3-9, 2019, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
In book, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, 01 Jun. 2017, Peer-reviwed
International conference proceedings, English - 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, May 2017, Peer-reviwed
Scientific journal, English - 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, Apr. 2017, Peer-reviwed
Scientific journal, English - 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, Apr. 2017, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - Extended formulations for sparsity matroids
Satoru Iwata; Naoyuki Kamiyama; Naoki Katoh; Shuji Kijima; Yoshio Okamoto
MATHEMATICAL PROGRAMMING, SPRINGER HEIDELBERG, 158, 1-2, 565-574, Jul. 2016, Peer-reviwed
Scientific journal, English - Computational Complexity of Sequential Token Swapping Problem (コンピュテーション)
山中 克久; ドメイン エリック; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 電子情報通信学会, 116, 116, 115-121, 24 Jun. 2016
English - シーケンシャルな交換による色付きトークン整列問題の計算複雑さ
山中 克久; エリック ドメイン; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
第158回アルゴリズム研究会, 1-7, Jun. 2016
Symposium, Japanese - 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, Jun. 2016, Peer-reviwed
Scientific journal, English - 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, Jan. 2016, Peer-reviwed
Scientific journal, English - On the treewidth of toroidal grids
Masashi Kiyomi; Yoshio Okamoto; Yota Otachi
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 198, 303-306, Jan. 2016, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Aug. 2015, Peer-reviwed
Scientific journal, English - 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, Jul. 2015, Peer-reviwed
Scientific journal, English - 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, Jun. 2015, Peer-reviwed
Scientific journal, English - 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, Aug. 2014, Peer-reviwed
Scientific journal, English - 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, Jun. 2014, Peer-reviwed
Scientific journal, English - Submodularity of minimum-cost spanning tree games
Masayuki Kobayashi; Yoshio Okamoto
NETWORKS, WILEY, 63, 3, 231-238, May 2014, Peer-reviwed
Scientific journal, English - 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, May 2014, Peer-reviwed
Scientific journal, English - グラフ上のラベル付きトークン整列問題
山中 克久; エリック; ドメイン(MIT; 伊藤 健洋; 川原純; 清見 礼; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 内澤 啓; 宇野 毅明(N
電子情報通信学会コンピュテーション研究会資料, 2014, 2, 5-12, Apr. 2014
Symposium, Japanese - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - The Geodesic Diameter of Polygonal Domains
Sang Won Bae; Matias Korman; Yoshio Okamoto
DISCRETE & COMPUTATIONAL GEOMETRY, SPRINGER, 50, 2, 306-329, Sep. 2013, Peer-reviwed
Scientific journal, English - 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, Jul. 2013, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Aug. 2012, Peer-reviwed
Scientific journal, English - 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, Aug. 2012, Peer-reviwed
Scientific journal, English - Reverse preferential spread in complex networks
Hiroshi Toyoizumi; Seiichi Tani; Naoto Miyoshi; Yoshio Okamoto
PHYSICAL REVIEW E, AMER PHYSICAL SOC, 86, 2, Aug. 2012, Peer-reviwed
Scientific journal, English - 単位正方形上の一意被覆問題に対する近似アルゴリズム
伊藤 健洋; 中野 眞一; 岡本 吉央; 大舘 陽太; 上原 隆平; 宇野 毅明; 宇野 裕之
電子情報通信学会コンピュテーション研究会, 95-101, Jun. 2012
Symposium, English - Guest editors' foreword
Otfried Cheong; Yoshio Okamoto
International Journal of Computational Geometry and Applications, 22, 1, 1-2, Feb. 2012, Peer-reviwed
Scientific journal, English - 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, Feb. 2012, Peer-reviwed
Scientific journal, English - Game Theory for Computer Scientists -Noncoop-erative Games (Advanced)-.
Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai; Yoshio Okamoto
Computer Software, 29, 3, 39-53, 2012, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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).
International conference proceedings, English - 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, Jul. 2011, Peer-reviwed, 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.
Scientific journal, English - 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, Apr. 2011, Peer-reviwed, 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.
Scientific journal, English - 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, Feb. 2011, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - Submodular fractional programming for balanced clustering
Yoshinobu Kawahara; Kiyohito Nagano; Yoshio Okamoto
PATTERN RECOGNITION LETTERS, ELSEVIER SCIENCE BV, 32, 2, 235-243, Jan. 2011, Peer-reviwed, 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
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Improved Bounds for Wireless Localization
Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
ALGORITHMICA, SPRINGER, 57, 3, 499-516, Jul. 2010, Peer-reviwed, 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.
Scientific journal, English - 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, Jun. 2010, Peer-reviwed, 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.
Scientific journal, English - 支配集合数え上げ問題とグラフクラス
来嶋 秀治; 岡本 吉央; 宇野 毅明
電子情報通信学会コンピュテーション研究会, 9-15, Apr. 2010
Symposium, English - 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, Peer-reviwed
Scientific journal, English - The Geodesic Diameter of Polygonal Domains
Sang Won Bae; Matias Korman; Yoshio Okamoto
ALGORITHMS-ESA 2010, SPRINGER-VERLAG BERLIN, 6346, 500-+, 2010, Peer-reviwed, 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.
International conference proceedings, English - Adaptive Algorithms for Planar Convex Hull Problems
Hee-Kap Ahn; Yoshio Okamoto
FRONTIERS IN ALGORITHMICS, SPRINGER-VERLAG BERLIN, 6213, 316-+, 2010, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Dec. 2009, Peer-reviwed, 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.
Scientific journal, English - 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, Nov. 2009, Peer-reviwed, 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.
Scientific journal, English - Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno
COMP2009-24, 109, 45-52, Jun. 2009
Symposium, English - 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, Feb. 2009, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - Local topology of the free complex of a two-dimensional generalized convex shelling
Yoshio Okamoto
DISCRETE MATHEMATICS, ELSEVIER SCIENCE BV, 308, 17, 3836-3846, Sep. 2008, Peer-reviwed, 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.
Scientific journal, English - Fair cost allocations under conflicts - a game-theoretic point of view
Yoshio Okamoto
DISCRETE OPTIMIZATION, ELSEVIER SCIENCE BV, 5, 1, 1-18, Feb. 2008, Peer-reviwed, 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.
Scientific journal, English - コーダルサンドイッチの列挙, ランダム生成, 数え上げについて
来嶋 秀治; 清見 礼; 岡本 吉央
数理解析研究所講究録 理論計算機科学の深化 : 新たな計算世界観を求めて, 1599, 148-153, 2008
Symposium, English - 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, Peer-reviwed, 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.
Scientific journal, English - Improved bounds for wireless localization
Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
ALGORITHM THEORY - SWAT 2008, SPRINGER-VERLAG BERLIN, 5124, 77-+, 2008, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Oct. 2007, Peer-reviwed, 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.
Scientific journal, English - Matroid representation of clique complexes
Kenji Kashiwabara; Yoshio Okamoto; Takeaki Uno
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 155, 15, 1910-1929, Sep. 2007, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
International conference proceedings, English - 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, Peer-reviwed
International conference proceedings, English - 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, Aug. 2006, Peer-reviwed, 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.
Scientific journal, English - 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, Jul. 2006, Peer-reviwed, 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.
Scientific journal, English - Core stability of minimum coloring games
Thomas Bietenhader; Yoshio Okamoto
MATHEMATICS OF OPERATIONS RESEARCH, INFORMS, 31, 2, 418-431, May 2006, Peer-reviwed, 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.
Scientific journal, English - 多目的最適化問題への列挙アルゴリズム理論からのアプローチ
岡本 吉央; 宇野 毅明
研究集会「最適化：モデリングとアルゴリズム」共同レポート, 15-25, Mar. 2006, Invited
Symposium, Japanese - 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, Jan. 2006, Peer-reviwed, 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.
Scientific journal, English - 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, Feb. 2005, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - Counting the Independent Sets of a Chordal Graph
岡本 吉央; 宇野 毅明; 上原 隆平
第96回情報処理学会アルゴリズム研究会, 17-24, Jul. 2004
Symposium, English - Traveling salesman games with the Monge property
Y Okamoto
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 138, 3, 349-369, Apr. 2004, Peer-reviwed, 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.
Scientific journal, English - Core stability of minimum coloring games
T Bietenhader; Y Okamoto
GRAPH -THEORETIC CONCEPTS IN COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 3353, 389-401, 2004, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - Submodularity of some classes of the combinatorial optimization games
Y Okamoto
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, SPRINGER HEIDELBERG, 58, 1, 131-139, Oct. 2003, Peer-reviwed, 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.
Scientific journal, English - 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, Sep. 2003, Peer-reviwed, 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.
Scientific journal, English - A greedy algorithm for convex geometries
K Kashiwabara; Y Okamoto
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 131, 2, 449-465, Sep. 2003, Peer-reviwed, 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.
Scientific journal, English - Fair cost allocations under conflicts - A game-theoretic point of view
Y Okamoto
ALGORITHMS AND COMPUTATION, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 2906, 686-695, 2003, Peer-reviwed, 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.
Scientific journal, English - 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, Peer-reviwed, 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.
Scientific journal, English - The free complex of a two-dimensional generalized convex shelling
Yoshio Okamoto
EUROCOMB'03 -- Abstracts, 289-293, 2003, Peer-reviwed
International conference proceedings, English - Matroid representation of clique complexes
K Kashiwabara; Y Okamoto; T Uno
COMPUTING AND COMBINATORICS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 2697, 192-201, 2003, Peer-reviwed, 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.
Scientific journal, English - Some properties of the core on convex geometries
Yoshio Okamoto
Mathematical Methods of Operations Research, 56, 377-386, 2002, Peer-reviwed
Scientific journal, English
MISC
- ネットワーク型交渉ゲームの安定化アルゴリズム
伊藤健洋; 垣村尚徳; 神山直之; 小林佑輔; 岡本吉央
28 Feb. 2016, 情報処理学会研究報告(Web), 2016, AL-157, VOL.2016‐AL‐157,NO.3 (WEB ONLY), Japanese, 201602218370461602 - 1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))
伊藤 健洋; 垣村 尚徳; 神山 直之; 小林 佑輔; 岡本 吉央
公益社団法人日本オペレーションズ・リサーチ学会, 26 Mar. 2015, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015, 44-45, Japanese, 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., Information Processing Society of Japan (IPSJ), 24 Feb. 2015, IPSJ SIG Notes, 2015, 2, 1-6, English, 0919-6072, 110009877668, AN1009593X - Weight Balancing on Boundaries and Skeletons (New Streams of Computation Theory and Algorithms)
Barba Luis; Cheong Otfried; Carufel Jean-Lou De; Dobbins Michael; Fleischer Rudolf; Kawamura Akitoshi; Korman Matias; Okamoto Yoshio; Pach Janos; Tang Yuan; Tokuyama Takeshi; Verdonschot Sander; Wang Tianhao
Kyoto University, May 2014, RIMS Kokyuroku, 1894, 45-52, Japanese, 1880-2818, 110009804829, AN00061013 - Guest editorial: Selected papers from ISAAC 2011
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
Sep. 2013, Algorithmica, 67, 1, 1-2, English, 0178-4617, 84879268935 - Computational complexity and an integer programming model of Shakashaka
DEMAINE Erik D.; OKAMOTO Yoshio; UEHARA Ryuhei; UNO Yushi
Shakashaka, one of the so-called "pencil-and-paper" puzzles like Sudoku, was proposed by Guten and has been popularized by the Japanese publisher Nikoli. The computational complexity of Shakashaka was not studied so far. We first prove that Shakashaka is NP-complete. Next we formulate Shakashaka as an integer programming problem. We apply the formulation to some instances appeared in a puzzle book, solve them by using an IP solver, and show the experimental results; each problem can be solved in a second., The Institute of Electronics, Information and Communication Engineers, 24 Apr. 2013, IEICE technical report. Theoretical foundations of Computing, 113, 14, 43-48, English, 0913-5685, 110009768472, AN10013152 - GUEST EDITORS' FOREWORD
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
WORLD SCIENTIFIC PUBL CO PTE LTD, Apr. 2013, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 23, 2, 73-74, English, Others, 0218-1959, 1793-6357, WOS:000327447000001 - グラフを通したパズル・ゲームの一般化
岡本 吉央
パズルやゲームの中には登場するモノの間の相互関係が重要になるものが多い.例えば,本特集における伊藤大雄氏の記事ではジャンケンにおける各手の関係を有向グラフとして見ることにより,その一般化を考察している.本稿ではほかの例として「アルクインの川渡りパズル」と「帽子パズル」を考察対象とする.この2つについては近年研究が進んでおり,そのなかで未解決である問題についても言及する., 公益社団法人日本オペレーションズ・リサーチ学会, 01 Mar. 2013, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 58, 3, 161-166, Japanese, 0030-3674, 110009594408, AN00364999 - On computing the nucleolus and the Shapley value of facility location games with two cost values
並河 雄紀; 岡本 吉央; 大舘 陽太
施設配置ゲームは施設配置問題から生じる協力ゲームである．この問題では，施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし，最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える．しかし，実際にそのような解を計算しようとすると，計算量理論の意味で難しいことが多い．本稿では，施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する．具体的には，施設の数が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., 22 Feb. 2013, 研究報告アルゴリズム（AL）, 2013, 3, 1-8, Japanese, 110009550136, AN1009593X - Game Theory for Computer Scientist : Mechanism Design (Advanced)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial focuses on designing a mechanism that achieves a socially desirable outcome or a goal of the designer that arises from some practical demands, as several advanced topics on <IT>mechanism design</IT> theory. We first briefly explains the theory of combinatorial auctions via the most well-known Vickrey-Clarke-Groves mechanism. Second, as an example that designs a new mechanism for a practical demand, we introduce false-name bids and illustrate how we improve a trivial robust mechanism against false-name bids. Furthermore, we explore models and several theoretical results on mechanisms of a keyword auction and a two-sided matching as other well-known topics of mechanism design theory., Japan Society for Software Science and Technology, 25 Jan. 2013, Computer Software, 30, 1, 34-52, Japanese, 0289-6540, 10031138249 - Game Theory for Computer Scientists - Cooperative Games
Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai; Yoshio Okamoto
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, Computer Software, 30, 2, 33-51, English, 0289-6540, 10031151473, 84883333397 - Game Theory for Computer Scientists — Cooperative Games —
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
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., Japan Society for Software Science and Technology, 2013, Computer Software, 30, 2, 2_33-2_51, Japanese, 0289-6540, 130004892257 - Game Theory for Computer Scientists : Mechanism Design (Basic)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial describes an overview of mechanism design theory, which investigates a rule or a protocol for multiple agents to make a social decision. The theory models the decision problem as a games of incomplete information, where each player cannot directly observe her opponents' types. Under the assumption that each agent behaves so as to maximize her individual utility, mechanism design theory analyzes how a player chooses her action under a mechanism, while designs a mechanism to achieve a socially desirable outcome or a goal of the designer. This tutorial first briefly explains games of incomplete information and the concept of mechanism design. Then, as a typical example, we focus on auctions that sell a single item and explain several theoretical results on mechanism design theory., Japan Society for Software Science and Technology, 25 Oct. 2012, Computer Software, 29, 4, 15-31, Japanese, 0289-6540, 10031077886 - On Computing the Nucleolus and the Shapley Value of Facility Location Games
NAMIKAWA Takanori; OKAMOTO Yoshio; OTACHI Yota
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, computaion 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 restrited to two values, we characterize a convex game, which has several nice properties. Furthermore, for general uncapacitated facility location games, we exhibit a case in which the nucleolus and the Shapley value coincide., The Institute of Electronics, Information and Communication Engineers, 24 Oct. 2012, IEICE technical report. Theoretical foundations of Computing, 112, 272, 25-32, Japanese, 0913-5685, 110009636909, AN10013152 - Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data
KIYOMI Masashi; OKAMOTO Yoshio; SAITOH Toshiki
We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B&B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B&B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. This article is a technical report without peer review, and its polished version will be published elsewhere., The Institute of Electronics, Information and Communication Engineers, 14 Jun. 2012, IEICE technical report. Theoretical foundations of Computing, 112, 93, 17-24, English, 0913-5685, 110009588447, AN10013152 - Enumeration Fundamentals and Basic Algorithms
OKAMOTO Yoshio
列挙問題とは,与えられた条件を満たすものを漏れなく,重複なく出力する問題である.本稿では,列挙問題を解くためのアルゴリズム設計技法として基礎的なものを紹介する.まず,列挙アルゴリズムの効率の良さの測り方を導入する.その後で,部分集合列挙問題を例題として,分割法,グレイコード,逆探索法という三つの設計技法を紹介する.最後に,効率の良い列挙アルゴリズムを設計することが難しい列挙問題とその理由について言及する., The Institute of Electronics, Information and Communication Engineers, 01 Jun. 2012, The Journal of the Institute of Electronics, Information, and Communication Engineers, 95, 6, 477-483, Japanese, 0913-5693, 110009457693, AN1001339X - Introduction of Game Theory for Computer Scientists
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
Japan Society for Software Science and Technology, 25 Apr. 2012, Computer Software, 29, 2, 65-68, Japanese, 0289-6540, 10030311272 - Game Theory for Computer Scientists : Noncooperative Games (Basic Theory)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
Game theory is a mathematical study of interaction among rational players. This tutorial presents an overview of noncooperative game theory, specifically games in normal-form. In noncooperative game theory in normal-form, multiple players independently and simultaneously select their actions so as to maximize their own utilities. The obtained utility of a player is determined by combination of her own action and the actions of other players. In noncooperative games, various equilibrium concepts have been developed to predict the result of a game. First, we introduce basic notations and equilibrium concepts in noncoperative games. If we explicitly represent a normal form game, the size of the representation grows exponentially as the number of players increases. Thus, we explain the algorithms/computational costs to efficiently find Nash equilibria in graphical games and congestion games, which have been proposed as concise representation schema., Japan Society for Software Science and Technology, 25 Apr. 2012, Computer Software, 29, 2, 69-84, Japanese, 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, Feb. 2012, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 22, 1, 1-2, English, Others, 0218-1959, WOS:000308707000001 - Game Theory for Computer Scientists —Noncooperative Games (Advanced)—
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial introduces Nash equilibrium which is the most important equilibrium concept in noncooperative games. In 2-player zero-sum normal form games, we can compute Nash equilibria in polynomial time in the number of pure strategies available to players. However, in complicated games in which players take turns choosing actions, the number of pure strategies becomes large. We explain algorithms that can compute Nash equilibria in complicated card games such as poker. On the other hand, it has not been shown whether Nash equlibria in 2-player general-sum games can be found in polynomial time. The concepts related to decision problems are not appropriate in order to discuss the computational complexity of finding Nash equilibria, since the existence of them has been already proven. Thus, we introduce the classes PPAD and PPAD-complete to characterize the complexity of computing Nash equilibria., Japan Society for Software Science and Technology, 2012, Computer Software, 29, 3, 3_39-3_53, Japanese, 0289-6540, 130004549284 - Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
OKAMOTO YOSHIO; OTACHI YOTA; UEHARA RYUHEI; UNO TAKEAKI
The Institute of Electronics, Information and Communication Engineers, 30 Aug. 2011, IEICE technical report, 111, 195, 31-38, English, 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
28 Feb. 2011, 研究報告アルゴリズム（AL）, 2011, 1, 1-8, English, 110008583076, AN1009593X - How to make a picturesque maze (Theoretical Computer Science and Its Applications)
Okamoto Yoshio; Uehara Ryuhei
Kyoto University, May 2009, RIMS Kokyuroku, 1649, 58-65, Japanese, 1880-2818, 110007105293, AN00061013 - 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
岡本 吉央; 宇野 毅明
公益社団法人日本オペレーションズ・リサーチ学会, 14 Mar. 2006, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2006, 212-213, Japanese, 110006168732, AN00351206 - 第4回 離散最適化と協力ゲーム(2)
毛利 裕昭; 岡本 吉央
公益社団法人日本オペレーションズ・リサーチ学会, 01 Feb. 2003, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 48, 2, 114-120, Japanese, 0030-3674, 110001183690, AN00364999
Books and other publications
- 応用数理ハンドブック
岡本吉央
Dictionary or encycropedia, Japanese, Joint work, 離散システム (近似アルゴリズム), 朝倉書店, 25 Oct. 2013 - Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra
Yoshio Okamoto
Japanese, Single translation, Springer Japan, 2010 - 離散数学のすすめ
Japanese, Joint work, 第3章「平面上の点集合から見た離散数学」, 現代数学社, 2010 - Encyclopedia of Algorithms
English, Joint work, Traveling Sales Person with Few Inner Points, Springer, 2008 - Lectures on Discrete Geometry
Yoshio Okamoto
Japanese, Single translation, Springer-Verlag Tokyo, 2005 - Lectures on Polytopes
Masahiro Hachimori; Yoshio Okamoto
Japanese, Joint translation, Springer-Verlag Tokyo, 2003
Courses
- Theory of Computation
The University of Electro-Communications - 計算理論
電気通信大学 - 情報・通信工学基礎
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 - 離散数学
The University of Electro-Communications - 離散数理工学
The University of Electro-Communications - キャリア教育演習
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 - 数理解析
電気通信大学
Affiliated academic society
Research Themes
- Product structures theorems and unified methods of algorithm design for geometrically constructed graphs
岡本 吉央
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), 23K10982
01 Apr. 2023 - 31 Mar. 2026 - Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration
伊藤 健洋; 川原 純; 岡本 吉央; 鈴木 顕
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Tohoku University, Grant-in-Aid for Transformative Research Areas (B), 本研究は，研究領域「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」の総括班であり，その目的は「班間連携の促進」と「外部への広報活動」の大きく２つである．これらを実現するために，下記の通り活動を行った． まず，本年度の領域会議を2020年10月30日と2021年3月23日の２回完全オンラインにて開催した．１０月の領域会議では，本研究領域の全体像をメンバーらと再確認した．３月の領域会議では，班間連携を促進するためにも，各計画研究班の半年間の研究動向を報告し合い，研究討論を行った．また，１０月，３月の領域会議ともに，同日に一般公開のシンポジウムも併催した．１０月の公開シンポジウムは，キックオフミーティングと銘打って，本研究領域の目的と計画を中心に解説した．３月の公開シンポジウムでは，招待講演も企画した． さらにオンラインでは，組合せ遷移のセミナー・勉強会を継続して行った．2020年度中には７回開催し，それらは全て一般公開している．セミナー・勉強会は，本研究領域のメンバーが自身の研究を紹介することで，その背景分野を互いに勉強し合い，班間連携の促進につなげることを目的としている． この他にもアウトリーチ活動として，本研究領域Webサイトの開設，ニュースレター創刊号の発行，電気通信大学主催の産学官連携イベントでの発表などを行った． また，大容量メモリ搭載計算サーバを設置し，本研究領域のメンバーが利用できるように環境整備を行った．, 20H05792
Oct. 2020 - Mar. 2023 - 数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ
Principal investigator
Oct. 2020 - Mar. 2023 - 大規模配位空間の最適化理論：離散構造論の視点を中心にして
Scientific research (C), general, Principal investigator
Apr. 2020 - Mar. 2023 - パラメータ化計算量による幾何近似アルゴリズム
JSPS, 二国間事業共同研究 (インド (DST) との共同研究)
2019 - 2021 - 内在構造に基づく大規模グラフの高速処理とその理論基盤構築
栢森情報科学振興財団, 研究助成
Jan. 2017 - Dec. 2018 - 計算幾何学と計算トポロジーが拓く新時代データ解析の理論基盤
Scientific research (C), general, Principal investigator
2015 - 2017 - 持続可能な発展のための資源配分メカニズム設計理論の構築
Scientific research (S), Coinvestigator
2012 - 2016 - 最適化技法との融合による計算限界解析法の深化
Scientific research on innovative areas, research under a proposed research project, Coinvestigator, 新学術領域研究（研究領域提案型）
2012 - 2016 - 厳密計算における信頼性とその理論保証のための数理的アプローチ
Young scientists (B), Principal investigator
2012 - 2014 - 大規模なセンサネットワーク位置推定問題の数値解法に関する研究
KOJIMA Masakazu; OKAMOTO Yoshio; MIYOSHI Naoto; YAMASHITA Makoto; FUJISAWA Katsuki
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Tokyo Institute of Technology, Scientific research (B), general, Coinvestigator, Sensor network localization (SNL) problems have attracted considerable research interests for a broad spectrum of applications such as environmental monitoring, traffic control and structural assessment. The problem is to estimate the locations of n sensors of unknown positions using given distances and some m sensors of known positions (called anchors) in a sensor network of m+n sensors. Finding the solutions of this problem is known to be NP-hard. Thus, approximating the solution of this problem has been dealt with from many angles. In this project, we have studied numerical methods based on the semidefinite programming (SDP) relaxation．The SDP relaxation can provide approximate solutions with accuracy, but the computational cost of solving SNL problems by the SDP relaxation becomes expensive rapidly as their sizes increase. To avoid this difficulty, we fully exploited the sparsity which were involved in large scale SNL problems and improved the performance of the SDP solver SDPA. As a final product, we released a software package SFSDP that can solve large-scale sensor network localization problems in high speed., 22310089
2010 - 2012 - 多面体的組合せ論に基づく数え上げアルゴリズム設計理論の構築
OKAMOTO Yoshio
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Young scientists (B), Principal investigator, Results on counting problems for graphs, counting problems for discrete and computational geometry, and their applications to optimization problems were obtained. For example, the computational complexity of counting the dominating sets in a graph was investigated from the perspective of graph classes, and a polynomial-time algorithm to find a global optimal solution to the distance function maximization was developed by efficiently enumerating all local optimal solutions. These results were presented in refereed international journals and refereed international conferences., 21700009
2009 - 2011 - グラフ・ネットワーク上のゲーム理論に対するアルゴリズム理論的厳密アプローチ
OKAMOTO Yoshio
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Young scientists (B), Principal investigator, グラフ・ネットワークに関わる協力ゲーム理論について,アルゴリズム理論・計算理論の観点から精緻な議論を行った.特に,最小彩色ゲームと呼ばれる費用分担問題に対して,今までに提案された公平な費用分担の中のいくつかが効率よく計算できることを示した.それに加えて,コア安定性問題に対する計算量理論的な解析も行った.さらに,最小費用全域木ゲームと呼ばれる費用分担問題に対して,公平費用分担が効率よく計算できるための十分条件である劣モジュラ性を満たす場合の考察をした., 18710130
2006 - 2008 - 実践的な列挙アルゴリズムの理論構築
宇野 毅明; 中野 眞一; 松井 泰子; 岡本 吉央; 清見 礼
日本学術振興会, 科学研究費助成事業, 国立情報学研究所, Scientific research on priority areas (planned), Coinvestigator, 研究分担者となったのは2004年度から．, 16092227
2004 - 2007
