研究者業績

加藤 直樹

カトウ ナオキ  (Naoki Katoh)

基本情報

所属
兵庫県立大学 社会情報科学部 教授 (学部長)
学位
工学博士(京都大学)

J-GLOBAL ID
201401070102380165
researchmap会員ID
7000008443

外部リンク

昭48京大・工・数理卒.昭52同大学院博士課程中退.
同年大阪成人病センター勤務. 昭56年神戸商科大・管理科学・講師.平3同教授. 平9京大工学研究科建築学専攻教授.平27関西学院大・理工学部教授, 組合せ最適化, 計算幾何学の研究に従事. 最近は、最速避難計画、組合せ剛性理論の研究に従事。平12Hao Wang Award受賞. 著書「数理計画法」, 「データマイニングとその応用」」など.

論文

 336
  • Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
    IEICE Trans. Inf. Syst. 107(6) 732-740 2024年  
  • Yuya Higashikawa, Naoki Katoh, Yuki Kobayashi
    International Journal of Computer Mathematics: Computer Systems Theory 1 2023年3月2日  
  • Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
    CCCG 191-196 2023年  
  • Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu
    FCT 262-275 2023年  
  • Sergey Bereg, Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni, Binhai Zhu
    COCOON (1) 220-231 2023年  
  • Hiroki Maegawa, Naoki Katoh, Yuki Tokuni, Yuya Higashikawa
    COCOA (1) 406-418 2023年  
  • Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni
    COCOA (1) 29-42 2023年  
  • 前川 浩基, 加藤 直樹, 歌田 知昭, 中澤 智博, 杉本 和也, 吉田 泰基, 中山 善夫, 石原 健, 阪本 真由美
    地域安全学会論文集 41 197-207 2022年11月  査読有り
  • Yuki Kataoka, Tomoyasu Takemura, Munehiko Sasajima, Naoki Katoh
    JMIR cancer 7(1) e26911 2021年3月10日  
    BACKGROUND: Chatbots are artificial intelligence-driven programs that interact with people. The applications of this technology include the collection and delivery of information, generation of and responding to inquiries, collection of end user feedback, and the delivery of personalized health and medical information to patients through cellphone- and web-based platforms. However, no chatbots have been developed for patients with lung cancer and their caregivers. OBJECTIVE: This study aimed to develop and evaluate the early feasibility of a chatbot designed to improve the knowledge of symptom management among patients with lung cancer in Japan and their caregivers. METHODS: We conducted a sequential mixed methods study that included a web-based anonymized questionnaire survey administered to physicians and paramedics from June to July 2019 (phase 1). Two physicians conducted a content analysis of the questionnaire to curate frequently asked questions (FAQs; phase 2). Based on these FAQs, we developed and integrated a chatbot into a social network service (phase 3). The physicians and paramedics involved in phase I then tested this chatbot (α test; phase 4). Thereafter, patients with lung cancer and their caregivers tested this chatbot (β test; phase 5). RESULTS: We obtained 246 questions from 15 health care providers in phase 1. We curated 91 FAQs and their corresponding responses in phase 2. In total, 11 patients and 1 caregiver participated in the β test in phase 5. The participants were asked 60 questions, 8 (13%) of which did not match the appropriate categories. After the β test, 7 (64%) participants responded to the postexperimental questionnaire. The mean satisfaction score was 2.7 (SD 0.5) points out of 5. CONCLUSIONS: Medical staff providing care to patients with lung cancer can use the categories specified in this chatbot to educate patients on how they can manage their symptoms. Further studies are required to improve chatbots in terms of interaction with patients.
  • 坂井 明日香, 丸橋 弘明, 羽室 行信, 笹嶋 宗彦, 加藤 直樹, 宇野 毅明
    人工知能学会論文誌 36(1) WI2-I_1 2021年1月1日  査読有り
  • Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, Junichi Teruyama
    21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems(ATMOS) 13-19 2021年  
  • Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Koji Watase
    Theoretical Computer Science 873 87-113 2021年  
  • Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
    Lecture Notes in Computer Science 244-256 2021年  
  • Tetsuya Fujie, Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni
    WALCOM: Algorithms and Computation - 15th International Conference and Workshops(WALCOM) 52-64 2021年  
  • Tetsuya Fujie, Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni
    CoRR abs/2011.13569 2020年  
  • Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Koji Watase
    CoRR abs/2010.05729 2020年  
  • Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Koji Watase
    Combinatorial Optimization and Applications - 14th International Conference(COCOA) 198-213 2020年  
  • Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    Theor. Comput. Sci. 806 388-401 2020年  査読有り
  • Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu
    CoRR abs/1910.01753 2019年  
  • Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    Theory and Applications of Models of Computation - 15th Annual Conference(TAMC) 42-58 2019年  
  • Naoki Katoh, Yuya Higashikawa, Hiro Ito, Shun Kataoka, Takuya Kida, Toshiki Saitoh, Tetsuo Shibuya, Kazuyuki Tanaka, Yushi Uno
    Rev. Socionetwork Strateg. 13(2) 99-100 2019年  
  • Yuya Higashikawa, Naoki Katoh
    Rev. Socionetwork Strateg. 13(2) 163-208 2019年  査読有り最終著者
  • Yosuke Hanawa, Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    Journal of Combinatorial Optimization 36(4) 1299-1314 2018年11月  査読有り招待有り
  • 加藤 直樹
    日本建築学会環境系論文集 83(745) 323-331 2018年3月1日  査読有り
  • Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    CoRR abs/1810.10631 2018年  
  • 加藤 直樹
    Proc. The 29th International Symposium on Algorithms and Computation (ISAAC 2018) 14-13 2018年  査読有り
  • Jeliazko R Jeliazkov, Adnan Sljoka, Daisuke Kuroda, Nobuyuki Tsuchimura, Naoki Katoh, Kouhei Tsumoto, Jeffrey J Gray
    Frontiers in immunology 9(413) 413-413 2018年  査読有り
    Antibodies can rapidly evolve in specific response to antigens. Affinity maturation drives this evolution through cycles of mutation and selection leading to enhanced antibody specificity and affinity. Elucidating the biophysical mechanisms that underlie affinity maturation is fundamental to understanding B-cell immunity. An emergent hypothesis is that affinity maturation reduces the conformational flexibility of the antibody's antigen-binding paratope to minimize entropic losses incurred upon binding. In recent years, computational and experimental approaches have tested this hypothesis on a small number of antibodies, often observing a decrease in the flexibility of the complementarity determining region (CDR) loops that typically comprise the paratope and in particular the CDR-H3 loop, which contributes a plurality of antigen contacts. However, there were a few exceptions and previous studies were limited to a small handful of cases. Here, we determined the structural flexibility of the CDR-H3 loop for thousands of recent homology models of the human peripheral blood cell antibody repertoire using rigidity theory. We found no clear delineation in the flexibility of naïve and antigen-experienced antibodies. To account for possible sources of error, we additionally analyzed hundreds of human and mouse antibodies in the Protein Data Bank through both rigidity theory and B-factor analysis. By both metrics, we observed only a slight decrease in the CDR-H3 loop flexibility when comparing affinity matured antibodies to naïve antibodies, and the decrease was not as drastic as previously reported. Further analysis, incorporating molecular dynamics simulations, revealed a spectrum of changes in flexibility. Our results suggest that rigidification may be just one of many biophysical mechanisms for increasing affinity.
  • Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    CoRR abs/1806.00814 2018年  査読有り
  • Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings 78-89 2018年  査読有り
  • Yuya Higashikawa, Siu-Wing Cheng, Tsunehiko Kameda, Naoki Katoh, Shun Saburi
    Theory of Computing Systems 62(6) 1-17 2017年5月27日  査読有り
    This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n3) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.
  • Xavier Gandibleux, Hiroyuki Morita, Naoki Katoh
    COMPUTERS & OPERATIONS RESEARCH 79 291-303 2017年3月  査読有り
    The paper presents a population-based algorithm for computing approximations of the efficient solution set for the linear assignment problem with two objectives. This is a multiobjective metaheuristic based on the intensive use of three operators a local search, a crossover and a path-relinking performed on a population composed only of elite solutions. The initial population is a set of feasible solutions, where each solution is one optimal assignment for an appropriate weighted sum of two objectives. Genetic information is derived from the elite solutions, providing a useful genetic heritage to be exploited by crossover operators. An upper bound set, defined in the objective space, provides one acceptable limit for performing a local search. Results reported using referenced data sets have shown that the heuristic is able to quickly find a very good approximation of the efficient frontier, even in situation of heterogeneity of objective functions. In addition, this heuristic has two main advantages. It is based on simple easy-to-implement principles, and it does not need a parameter tuning phase. (C) 2017 Published by Elsevier Ltd.
  • S. W. Cheng, Y. Higashikawa, N. Katoh, A. Sljoka
    Proceedings of The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2017) 93-102 2017年  査読有り
  • 瀧澤重志, 加藤直樹
    日本不動産学会 31(1) 58-63 2017年  査読有り
  • Binay Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10389 133-144 2017年  査読有り
    We address the problem of locating k sinks on dynamic flow path networks with n vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in O(n log n + k2 log4 n) and O(n log3 n) time, respectively. When all edges have the same capacity, we also present two algorithms which run in O(n + k2 log2 n) time and O(n log n) time, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities O(kn log2 n) [1] and O(kn) [11], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/ merging them in an efficient manner.
  • Naoki Katoh, Hee-Kap Ahn, Subhas C Nandy
    NII Shonan Meet. Rep. 2017 2017年  査読有り
  • Binay Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10389 133-144 2017年  査読有り
    We address the problem of locating k sinks on dynamic flow path networks with n vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in O(n log n + k2 log4 n) and O(n log3 n) time, respectively. When all edges have the same capacity, we also present two algorithms which run in O(n + k2 log2 n) time and O(n log n) time, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities O(kn log2 n) [1] and O(kn) [11], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/ merging them in an efficient manner.
  • 瀧澤重志, 池上純代, 加藤直樹
    日本建築学会計画系論文集 81(728) 2259-2268 2016年10月  査読有り
  • 加藤 直樹
    電子情報通信学会和文誌D, 199-D(10) 1055-1068 2016年10月  査読有り
  • Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, Yoshio Okamoto
    MATHEMATICAL PROGRAMMING 158(1-2) 565-574 2016年7月  査読有り
    We show the existence of a polynomial-size extended formulation for the base polytope of a -sparsity matroid. For an undirected graph , the size of the formulation is when and when . To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.
  • Naoki Katoh, Atsushi Takizawa
    Contrast Data Mining: Concepts, Algorithms, and Applications 337-350 2016年4月19日  
  • Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh, Adnan Sljoka
    INFORMATION PROCESSING LETTERS 116(2) 175-178 2016年2月  査読有り
    In this paper, we characterize the redundant rigidity and the redundant global rigidity of body-hinge graphs in R-d in terms of graph connectivity. Although an efficient algorithm which determines mixed-connectivity is still not known, our result implies that both edge-redundancy for rigidity and edge-redundancy for global rigidity can be checked via efficient graph-connectivity algorithms. (C) 2015 Elsevier B.V. All rights reserved.
  • Binay Bhattacharya, Ante Custic, Sandip Das, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 9943 24-36 2016年  査読有り
    We first consider the weighted p-center problem, in which the centers are constrained to lie on two axis-parallel lines. Given a set of n points in the plane, which are sorted according to their x-coordinates, we show how to test in O(n log n) time if p piercing points placed on two lines, parallel to the x-axis, can pierce all the disks of different radii centered at the n given points. This leads to an O(n log(2) n) time algorithm for the weighted p-center problem. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithm runs in O(n log(2) n) time in this case as well.
  • Yuya Higashikawa, Siu-Wing Cheng, Tsunehiko Kameda, Naoki Katoh, Shun Saburi
    Combinatorial Algorithms 9843 122-134 2016年  査読有り
    This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n(3)) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.
  • Takashi Horiyama, Jin-ichi Itoh, Naoki Katoh, Yuki Kobayashi, Chie Nara
    DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 9943 120-131 2016年  査読有り
    Itoh and Nara [3] discussed with Kobayashi the continuous flattening of all Platonic polyhedra; however, a problem was encountered in the case of the dodecahedron. To complete the study, we explicitly show, in this paper, a continuous folding of a regular dodecahedron following the ideas in [3].
  • Binay Bhattacharya, Ante Custic, Sandip Das, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh
    DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 9943 24-36 2016年  査読有り
    We first consider the weighted p-center problem, in which the centers are constrained to lie on two axis-parallel lines. Given a set of n points in the plane, which are sorted according to their x-coordinates, we show how to test in O(n log n) time if p piercing points placed on two lines, parallel to the x-axis, can pierce all the disks of different radii centered at the n given points. This leads to an O(n log(2) n) time algorithm for the weighted p-center problem. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithm runs in O(n log(2) n) time in this case as well.
  • Guru Prakash Arumugam, John Augustine, Mordecai, J. Golin, Yuya Higashikawa, Naoki Katoh, Prashanth Srikanthan
    CoRR abs/1606.07208 2016年  査読有り
  • Yuya Higashikawa, Siu-Wing Cheng, Tsunehiko Kameda, Naoki Katoh, Shun Saburi
    Combinatorial Algorithms 9843 122-134 2016年  査読有り
    This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative vertex supplies. Here, each vertex supply is unknown but only an interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Given a scenario s and a sink location x in a dynamic path network, let us consider the evacuation time to x of a unit supply given on a vertex by s. The cost of x under s is defined as the sum of evacuation times to x for all supplies given by s, and the median under s is defined as a sink location which minimizes this cost. The regret for x under s is defined as the cost of x under s minus the cost of the median under s. Then, the problem is to find a sink location such that the maximum regret for all possible scenarios is minimized. We propose an O(n(3)) time algorithm for the minimax regret 1-median problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.
  • Yosuke Hanawa, Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10043 18-52 2016年  査読有り
    A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then, the goal of this problem is to find a minimum time limit such that we can send exactly the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.
  • Sergey Bereg, Seok-Hee Hong, Naoki Katoh, Sheung-Hung Poon, Shin-ichi Tanigawa
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 51 15-24 2016年1月  査読有り
    This paper is concerned with the crossing number of Euclidean minimum-weight Laman graphs in the plane. We first investigate the relation between the Euclidean minimum-weight Laman graph and proximity graphs, and then we show that the Euclidean minimum-weight Laman graph is quasi-planar and 6-planar. Thus the crossing number of the Euclidean minimum-weight Laman graph is linear in the number of points. (C) 2015 Elsevier B.V. All rights reserved.
  • Yoshihiko Ito, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh, Sheung-Hung Poon, Maria Saumell
    THEORETICAL COMPUTER SCIENCE 607 337-350 2015年11月  査読有り
    We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces matches the lower bound given by Gaspar, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1]. (C) 2015 Elsevier B.V. All rights reserved.

MISC

 240

書籍等出版物

 32

講演・口頭発表等

 8

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

 35

産業財産権

 1