Researcher Database

Researcher Profile and Settings

Master

Affiliation (Master)

  • Faculty of Information Science and Technology Computer Science and Information Technology Knowledge Software Science

Affiliation (Master)

  • Faculty of Information Science and Technology Computer Science and Information Technology Knowledge Software Science

researchmap

Profile and Settings

Affiliation

  • Hokkaido University, Faculty of Information Science and Technology, Professor

Degree

  • Ph. D.(Kyoto University)

Profile and Settings

  • Name (Japanese)

    Horiyama
  • Name (Kana)

    Takashi
  • Name

    200901003225304650

Alternate Names

Affiliation

  • Hokkaido University, Faculty of Information Science and Technology, Professor

Achievement

Research Areas

  • Informatics / Information theory
  • Informatics / Information theory
  • Informatics / Information theory
  • Informatics / Information theory

Research Experience

  • 2019/09 - Today Hokkaido University Faculty of Information Science and Technology Professor
  • 2007/04 - 2019/08 Saitama University Graduate School of Science and Engineering Associate Professor
  • 2002/07 - 2007/03 Kyoto University Graduate School of Informatics Research Associate
  • 1999/04 - 2002/06 Nara Institute of Science and Technology Graduate School of Information Science Research Associate

Education

  • 1998/10 - 1999/03  Kyoto University  Graduate School of Engineering  Department of Applied Mathematics and Physics
  • 1995/04 - 1998/09  Kyoto University  Graduate School of Engineering  Department of Information Science
  • 1991/04 - 1995/03  Kyoto University  Faculty of Engineering  Department of Information Science

Committee Memberships

  • 2004/05 -2008/04   -   The Institute of Electronics, Information and Communication Engineers

Awards

  • 2018/09 電子情報通信学会基礎境界ソサイエティ, 貢献賞
  • 2016/05 電子情報通信学会情報・システムソサイエティ, 情報・システムソサイエティ論文編集活動感謝状
  • 2016/05 情報処理学会, 感謝状
  • 2011/02 The 9th EATCS/LA Workshop on Theoretical Computer Science, EATCS/LA Best Presentation Award
  • 2001/03 電子情報通信学会 学術奨励賞
  • 2000/05 日経BP社 LSI IPデザイン・アワード IP賞
     
    受賞者: 中村一博;朱強;丸岡新治;堀山貴史;木村晋二;渡邉勝正

Published Papers

  • Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
    CoRR abs/2402.17428 2024
  • Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
    CPM 24 - 15 2024
  • Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
    IEICE Trans. Inf. Syst. 107 (6) 732 - 740 2024
  • Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki
    AAAI 20726 - 20734 2024
  • Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
    Theoretical Computer Science 114183 - 114183 0304-3975 2023/09
  • Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, Takashi Horiyama
    WALCOM: Algorithms and Computation 127 - 138 0302-9743 2023/03 [Refereed]
  • Yuki Kawakami, Shun Takahashi, Kazuhisa Seto, Takashi Horiyama, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh
    CCCG 191 - 196 2023
  • Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki
    CoRR abs/2312.10599 2023
  • TERUI Shunta, YAMANAKA Katsuhisa, HIRAYAMA Takashi, HORIYAMA Takashi, KURITA Kazuhiro, UNO Takeaki
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences to appear 0916-8508 2023 [Refereed]
     
    We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2 |ϵ(S) |)-time, where ϵ(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surrounding polygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon.
  • Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
    Journal for Geometry and Graphics, 26 (1) 81 - 100 1433-8157 2022/07 [Refereed]
     
    In this paper, we show geometric properties of a family of polyhedra obtained by folding a regular tetrahedron along triangular grids. Each polyhedron is identified by a pair of nonnegative integers. The polyhedron can be cut along a geodesic strip of triangles to be decomposed and unfolded into one or multiple bands. We show that the number of bands is the greatest common divisor of the two integers. By a proper choice of pairs of numbers, a common triangular band that folds into different multiple polyhedra can be created. We construct the configuration of the polyhedron algebraically and numerically through angular and truss models respectively. We discuss the volumes of the obtained folded states and provide relevant open problems regarding the existence of popped-up state. We also show some geometric connections to other art forms.
  • Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, Ryuhei Uehara
    DISCRETE & COMPUTATIONAL GEOMETRY 0179-5376 2022/07 [Refereed]
     
    We investigate a folding problem that inquires whether a polygon P can be folded, without overlap or gaps, onto a polyhedron Q for given P and Q. An efficient algorithm for this problem when Q is a box was recently developed. We extend this idea to a class of convex polyhedra, which includes the five regular polyhedra, known as Platonic solids. Our algorithms use a common technique, which we call stamping. When we apply this technique, we use two special vertices shared by both P and Q (that is, there exist two vertices of P that are also vertices of Q). All convex polyhedra and their developments have such vertices, except a special class of tetrahedra, the tetramonohedra. We develop two algorithms for the problem as follows. For a given Q, when Q is not a tetramonohedron, we use the first algorithm which solves the folding problem for a certain class of convex polyhedra. On the other hand, if Q is a tetramonohedron, we use the second algorithm to handle this special case. Combining these algorithms, we can conclude that the folding problem can be solved in pseudo-polynomial time when Q is a polyhedron in a certain class of convex polyhedra that includes regular polyhedra.
  • Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka
    Computational Geometry 104 101860  0925-7721 2022/06 [Refereed]
  • Takuya Mieno, Shunsuke Inenaga, Takashi Horiyama
    CPM 26 - 17 2022 [Refereed]
  • Max-Min 3-dispersion Problems
    Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 303 305 - 313 2021/11 [Refereed]
  • Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Isao Tanaka
    PHYSICAL REVIEW MATERIALS 5 (11) 2475-9953 2021/11 [Refereed]
     
    The advanced data structure of the zero-suppressed binary decision diagram (ZDD) enables us to efficiently enumerate nonequivalent substitutional structures. Not only can the ZDD store a vast number of structures in a compressed manner, but also a set of structures satisfying given constraints can be extracted from the ZDD efficiently. Here, we present a ZDD-based efficient algorithm for exhaustively searching for special quasirandom structures (SQSs) that mimic the perfectly random substitutional structure. We demonstrate that the current approach can extract only a tiny number of SQSs from a ZDD composed of many substitutional structures (>10(12)). As a result, we find SQSs that are optimized better than those proposed in the literature. A series of SQSs should be helpful for estimating the properties of substitutional solid solutions. Furthermore, the present ZDD-based algorithm should be useful for applying the ZDD to the other structure enumeration problems.
  • Katsuhisa Yamanaka, David Avis, Takashi Horiyama, Yoshio Okamoto, Ryuhei Uehara, Tanami Yamauchi
    Discrete Applied Mathematics 303 305 - 313 0166-218X 2021/11 [Refereed][Not invited]
  • Masashi Kiyomi, Takashi Horiyama, Yota Otachi
    Information Processing Letters 168 106084  2021 [Refereed]
  • Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa
    Theoretical Computer Science 859 57 - 69 0304-3975 2021/01 [Refereed]
  • Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, Isao Tanaka
    JOURNAL OF CHEMICAL PHYSICS 153 (10) 0021-9606 2020/09 [Refereed]
     
    A derivative structure is a nonequivalent substitutional atomic configuration derived from a given primitive cell. The enumeration of derivative structures plays an essential role in searching for the ground states in multicomponent systems. However, it is computationally difficult to enumerate derivative structures if the number of derivative structures of a target system becomes huge. In this study, we introduce a novel compact data structure of the zero-suppressed binary decision diagram (ZDD) for enumerating derivative structures much more efficiently. We show its simple applications to the enumeration of structures derived from the face-centered cubic and hexagonal close-packed lattices in binary, ternary, and quaternary systems. The present ZDD-based procedure should contribute to computational approaches based on derivative structures in physics and materials science.
  • Hugo Alves Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi
    Journal of Computational Geometry 11 (1) 93 - 124 2020 [Refereed]
  • Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara
    Journal of Graph Algorithms and Applications 24 (2) 89 - 103 2020 [Refereed]
  • Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, Ryuhei Uehara
    Proceedings of the 32nd Canadian Conference on Computational Geometry(CCCG) 121 - 127 2020
  • Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato
    In Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020) 12049 211 - 222 2020 [Refereed][Not invited]
  • Geodesic Folding of Tetrahedron
    Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
    Symmetry: Art and Science, 11th Congress and Exhibition 2019/11
  • Sequentially Swapping Colored Tokens on Graphs
    Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamo, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno
    Journal of Graph Algorithms and Applications 23 (1) 3 - 27 2019/01 [Refereed]
  • Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, Katsuhisa Yamanaka
    Proceedings of the 31st Canadian Conference on Computational Geometry(CCCG) 177 - 183 2019
  • Koichi Mizunashi, Takashi Horiyama, Ryuhei Uehara
    WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings Springer 277 - 288 2019 [Refereed][Not invited]
  • Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
    Lecture Notes in Computer Science 104-A (9) 291 - 300 0302-9743 2019
  • Yu NAKAHATA, Jun KAWAHARA, Takashi HORIYAMA, Shoji KASAHARA
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E101.A (9) 1363 - 1374 0916-8508 2018/09/01 [Refereed][Not invited]
  • Dawei Xu, Jinfeng Huang, Yuta Nakane, Tomoo Yokoyama, Takashi Horiyama, Ryuhei Uehara
    IEICE Transactions 101-A (9) 1420 - 1430 0916-8508 2018/09 [Refereed][Not invited]
  • Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno, Kunihiro Wasa
    The proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018) 61 - 67 2018/08 [Refereed][Not invited]
  • Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
    Theoretical Computer Science 729 1 - 10 0304-3975 2018/06/12 [Refereed][Not invited]
     
    We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,…,c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for c=3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.
  • Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa
    Proc. of the 12th International Frontiers of Algorithmics Workshop (FAW 2018), Lecture Notes in Computer Science 10823 263 - 272 0302-9743 2018/03 [Refereed]
  • Hugo A. Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi
    CoRR abs/1812.01160 2018
  • Takashi Horiyama, Masahiro Miyasaka, Riku Sasaki
    Proceedings of the 30th Canadian Conference on Computational Geometry(CCCG) 360 - 366 2018
  • Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara
    Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings Springer 177 - 188 2018 [Refereed][Not invited]
  • Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
    Journal of Information Processing 25 708 - 715 1882-6652 2017/08/01 [Refereed][Not invited]
     
    We study a combinatorial game named '‘sankaku-tori’' in Japanese, which means '‘triangle-taking’' in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.
  • Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 64 1 - 12 0925-7721 2017/08 [Refereed][Not invited]
     
    We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that fold into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, and the smallest possible surface area for three different boxes is 46. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge to search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1 x 1 x 7 and 1 x 3 x 3. Moreover, when we fold along diagonal lines of rectangles of size 1 x 2, this area 30 may admit to fold into a box of size root 5 x root 5 x root 5. The results are summarized as follows. There exist 1,080 common developments of two boxes of size 1 x 1 x 7 and 1 x 3 x 3. Among them, there are nine common developments of three boxes of size 1 x 1 x 7, 1 x 3 x 3, and root 5 x root 5 x root 5. Interestingly, one of nine such polygons folds into three different boxes 1 x 1 x 7, 1 x 3 x 3, and root 5 x root 5 x root 5 in four different ways. (C) 2017 Elsevier B.V. All rights reserved.
  • On the Enumeration of Chequered Tilings in Polygons
    Hiroaki Hamanaka, Takashi Horiyama, Ryuhei Uehara
    Proc. of Bridges 2017 conference 423 - 426 2017/07 [Refereed]
  • Takashi Horiyama
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 100-A (9) 1763 - 1763 2017
  • Jun Kawahara, Takashi Horiyama, Keisuke Hotta, Shin-ichi Minato
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017 10167 119 - 131 0302-9743 2017 [Refereed][Not invited]
     
    A balanced graph partition on a vertex-weighted graph is a partition of the vertex set such that the partition has k parts and the disparity, which is defined as the ratio of the maximum total weight of parts to the minimum one, is at most r. In this paper, a novel algorithm is proposed that enumerates all the graph partitions with small disparity. Experimental results show that five millions of partitions with small disparity for some graph with more than 100 edges can be enumerated within ten minutes.
  • Dawei Xu, Takashi Horiyama, Ryuhei Uehara
    Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada 62 - 67 2017 [Refereed][Not invited]
  • Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
    Discrete & Computational Geometry 58 (3) 686 - 704 2017 [Refereed][Not invited]
  • Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno
    Proc. of WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017 LNCS 10167 (1) 435 - 447 0302-9743 2017 [Refereed][Not invited]
     
    We consider a puzzle consisting of colored tokens on an nvertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to "sequentially" move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n(3)) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles.
  • Nagahata Y, Maeda S, Teramoto H, Horiyama T, Taketsugu T, Komatsuzaki T
    The journal of physical chemistry. B 120 (8) 1961 - 1971 1520-6106 2016/03 [Refereed][Not invited]
     
    Markovian dynamics on complex reaction networks are one of the most intriguing subjects in a wide range of research fields including chemical reactions, biological physics, and ecology. To represent the global kinetics from one node (corresponding to a basin on an energy landscape) to another requires information on multiple pathways that directly or indirectly connect these two nodes through the entire network. In this paper we present a scheme to extract a hierarchical set of global transition states (TSs) over a discrete time Markov chain derived from first-order rate equations. The TSs can naturally take into account the multiple pathways connecting any pair of nodes. We also propose a new type of disconnectivity graph (DG) to capture the hierarchical organization of different time scales of reactions that can capture changes in the network due to changes in the observation. The crux is the introduction of the minimum conductance cut (MCC) in graph clustering, corresponding to the dividing surface across the network having the "smallest" transition probability between two disjoint subnetworks (superbasins on the energy landscape) in the network. We present a new combinatorial search algorithm for finding this MCC. We apply our method to a reaction network of Claisen rearrangement of allyl vinyl ether that consists of 23 nodes and 66 links (saddles on the energy landscape) connecting them. We compare the kinetic properties of our DG to those of the transition matrix of the rate equations and show that our graph can properly reveal the hierarchical, organization of time scales in a network.
  • Takashi Horiyama, Jin-ichi Itoh, Naoki Katoh, Yuki Kobayashi, Chie Nara
    DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 9943 120 - 131 0302-9743 2016 [Refereed][Not invited]
     
    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].
  • Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara
    Journal of Graph Algorithms and Applications 20 (1) 101 - 104 1526-1719 2016 [Refereed][Not invited]
     
    In this paper, we investigate the common unfolding between regular tetrahedra and Johnson-Zalgaller solids. More precisely, we investigate the sets of all edge developments of Johnson-Zalgaller solids that fold into regular tetrahedra. We show that, among 92 Johnson-Zalgaller solids, only J17 (gyroelongated square dipyramid) and J84 (snub disphenoid) have some edge developments that fold into a regular tetrahedron, and the remaining Johnson-Zalgaller solids do not have any such edge development.
  • Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi, Ryuhei Uehara
    DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 9943 167 - 179 0302-9743 2016 [Refereed][Not invited]
     
    Flat foldability of general crease patterns was first claimed to be hard for over twenty years. In this paper we prove that deciding flat foldability remains NP-complete even for box pleating, where creases form a subset of a square grid with diagonals. In addition, we provide new terminology to implicitly represent the global layer order of a flat folding, and present a new planar reduction framework for grid-aligned gadgets.
  • Takashi Horiyama, Ryuhei Uehara, Haruo Hosoya
    8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 20:1-20:14 - 14 2016 [Refereed][Not invited]
  • 正4 面体と立方体の共通の展開図に関する研究
    白川俊博, 堀山貴史, 上原隆平
    日 本折紙学会, 折り紙の科学 4 (1) 45 - 54 2015/03 [Refereed]
  • Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015) 9076 236 - 247 0302-9743 2015 [Refereed][Not invited]
     
    We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that folds into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, which admits to fold into two boxes of size 1x1x5 and 1x2x3. On the other hand, the smallest possible surface area for three different boxes is 46, which may admit to fold into three boxes of size 1x1x11, 1x2x7, and 1x3x5. For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge for search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size 1x1x7 and 1x3x3. Moreover, when we admit to fold along diagonal lines of rectangles of size 1x2, the area may admit to fold into a box of size root 5x root 5x root 5. That is, the area 30 is the smallest candidate area for folding three different boxes in this manner. We perform two algorithms. The first algorithm is based on ZDDs, zero-suppressed binary decision diagrams, and it computes in 10.2 days on a usual desktop computer. The second algorithm performs exhaustive search, however, straightforward implementation cannot be run even on a supercomputer since it causes memory overflow. Using a hybrid search of DFS and BFS, it completes its computation in 3 months on a supercomputer. As results, we obtain (1) 1,080 common developments of two boxes of size 1x1x7 and 1x3x3, and (2) 9 common developments of three boxes of size 1x1x7, 1x3x3, and root 5 x root 5 x root 5.
  • Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara
    WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings Springer 8973 294 - 305 0302-9743 2015 [Refereed][Not invited]
     
    Common unfolding of a regular tetrahedron and a Johnson-Zalgaller solid is investigated. More precisely, we investigate the sets of all edge unfoldings of Johnson-Zalgaller solids. Among 92 Johnson-Zalgaller solids, some of edge unfolding of J17 and J84 admit to fold into a regular tetrahedron. On the other hand, there are no edge unfolding of the other Johnson-Zalgaller solids that admit to fold into a regular tetrahedron.WALCOM: Algorithms and Computation, 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings
  • Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9214 619 - 628 1611-3349 2015 [Refereed][Not invited]
     
    We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees.
  • Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
    Theoretical Computer Science 555 71 - 84 0304-3975 2014/10 [Refereed][Not invited]
     
    A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved.
  • Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, Ryuhei Uehara
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E97A (6) 1206 - 1212 1745-1337 2014/06 [Refereed][Not invited]
     
    We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
  • Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
    FUN WITH ALGORITHMS 8496 230 - 239 0302-9743 2014 [Refereed][Not invited]
     
    We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.
  • ABEL ZACHARY, DEMAINE ERIK D., DEMAINE MARTIN L., HORIYAMA TAKASHI, UEHARA RYUHEI
    Lecture Notes in Computer Science 一般社団法人電子情報通信学会 113 (50) 33 - 38 0913-5685 2013/05/17 
    We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
  • Takashi Horiyama, Wataru Shoji
    Algorithms and Computation - 24th International Symposium(ISAAC) 623 - 633 2013
  • Atsushi Takizawa, Yasufumi Takechi, Akio Ohta, Naoki Katoh, Takeru Inoue, Takashi Horiyama, Jun Kawahara, Shin-Ichi Minato
    Proc. of the 11th International Symposium on Operations Research and its Applications in engineering, technology and management 64 - 71 2013 [Refereed][Not invited]
     
    Japanese cities always have risks of large-scale earthquakes. Thus, it is very important to establish crisis management systems against large-scale disasters such as big earthquakes, and tsunamis to secure evacuation centers for evacuees. In this respect, it is extremely important to provide sufficient evacuation centers and to appropriately partition the whole region into small areas, such that a unique evacuation center is located in each area and the people living in the area can easily evacuate to the center. However, it is hard to find an optimal region partitioning, due to the uncertainty, such as a fire or collapsed buildings. In this research, we propose a method to enumerate all partitioning patterns using Zero-suppressed Binary Decision Diagram (ZDD) that satisfy several conditions. We apply the proposed method to Kamigyo Ward of Kyoto City, Japan. © 2013 IET.
  • Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
    WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings Springer 7748 53 - 64 0302-9743 2013 [Refereed][Not invited]
     
    The problem of decomposing a pixel grid into base-monotoneregions was first studied in the context of image segmentation. It is known that for a given n × n pixel grid and baselines, one can compute in O(n^3) time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. To complement this fact, we first show the NP-hardness of the problem of optimally locating k baselines in a given pixel grid. Next we present an O(n^3)-time 2-approximation algorithm for this problem. We also study some polynomial-time solvable cases, and variants of the problem.WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings
  • Xin Man, Takashi Horiyama, Shinji Kimura
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E95A (8) 1347 - 1358 0916-8508 2012/08 [Refereed][Not invited]
     
    Clock gating is supported by commercial tools as a power optimization feature based on the guard signal described in HDL (structural method). However, the identification of control signals for gated registers is hard and designer-intensive work. Besides, since the clock gating cells also consume power, it is imperative to minimize the number of inserted clock gating cells and their switching activities for power optimization. In this paper, we propose an automatic multi-stage clock gating algorithm with ILP (Integer Linear Programming) formulation, including clock gating control candidate extraction, constraints construction and optimum control signal selection. By multi-stage clock gating, unnecessary clock pulses to clock gating cells can be avoided by other clock gating cells, so that the switching activity of clock gating cells can be reduced. We find that any multi-stage control signals are also single-stage control signals, and any combination of signals can be selected from single-stage candidates. The proposed method can be applied to 3 or more cascaded stages. The multi-stage clock gating optimization problem is formulated as constraints in LP format for the selection of cascaded clock-gating order of multi-stage candidate combinations, and a commercial ILP solver (IBM CPLEX) is applied to obtain the control signals for each register with minimum switching activity. Those signals are used to generate a gate level description with guarded registers from original design, and a commercial synthesis and layout tools are applied to obtain the circuit with multi-stage clock gating. For a set of benchmark circuits and a Low Density Parity Check (LDPC) Decoder (6.6k gates, 212 F.F.s), the proposed method is applied and actual power consumption is estimated using Synopsys NanoSim after layout. On average, 31% actual power reduction has been obtained compared with original designs with structural clock gating, and more than 10% improvement has been achieved for some circuits compared with single-stage optimization method. CPU time for optimum multi-stage control selection is several seconds for up to 25k variables in LP format. By applying the proposed clock gating, area can also be reduced since the multiplexors controlling register inputs are eliminated.
  • Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
    Proceedings of the 24th Canadian Conference on Computational Geometry(CCCG) 211 - 216 2012
  • Xin Man, Takashi Horiyama, Shinji Kimura
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E93A (12) 2472 - 2480 0916-8508 2010/12 [Refereed][Not invited]
     
    Clock gating is the insertion of control signal for registers to switch off unnecessary clock signals selectively without violating the functional correctness of the original design so as to reduce the dynamic power consumption Commercial EDA tools usually have a mechanism to generate clock gating logic based on the structural method where the con trol signals specified by designers are used and the effectiveness of the clock gating depends on the specified control signals In the research we focus on the automatic clock gating logic generation and propose a method based on the candidate extraction and control signal selection We formalize the control signal selection using linear formulae and devise an optimization method based on BDD The method is effective for circuits with a lot of shared candidates by different registers The method is applied to counter circuits to check the co relation with power simulation results and a set of benchmark circuits 19 1-71 9% power reduction has been found on counter circuitsafter layout and 2 3-18 0% cost reduction on benchmark circuits
  • Takashi Horiyama, Shogo Yamane
    Computational Geometry, Graphs and Applications - 9th International Conference(CGGA) 96 - 107 2010
  • Takashi Horiyama, Masato Samejima
    Proceedings of the 21st Annual Canadian Conference on Computational Geometry(CCCG) 29 - 32 2009
  • Fine-Grained Power Gating Based on the Controlling Value of Logic Elements
    Lei Chen, Takashi Horiyama, Yuichi Nakamura, Shinji Kimura
    IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences E91-A (12) 3531 - 3538 2008/12 [Refereed]
  • Takashi Horiyama, Hiro Ito, Kazuo Iwama, Jun Kawahara
    INTERNATIONAL CONFERENCE ON INFORMATICS EDUCATION AND RESEARCH FOR KNOWLEDGE-CIRCULATING SOCIETY, PROCEEDINGS 193 - + 2008 [Refereed][Not invited]
     
    With the advances of modern computer technologies and elaborated algorithm design methodologies, it becomes important to enumerate all feasible solutions for given constraints. In this paper, we propose algorithms for enumerating Tsume-Shogi diagrams (i.e., Shogi. mating problems) by the reverse method. Conventional algorithms always take the principle 'generate candidate diagrams and sieve them by Tsume-Shogi solvers,' which tends to require lengthy execution time. In our approach, the reverse method enables us to enumerate all diagrams without using Tsume-Shogi solvers. We can sieve the candidates easily and quickly, since the), are generated in the ascending order according to the number of necessary moves for mating the defender's king. We have implemented the proposed algorithms, and enumerated all diagrams with several restrictions (e.g., those with only four knights). From this result, we prove many results for knight diagrams, e.g., i) the maximum number of moves is 11, ii) it is 13 for additional mate free, iii) it is 7 if at least one piece is in hand of the attacker, and iv) the maximum pieces in hand of the attacker is two.
  • Nobuhiro Doi, Takashi Horiyama, Masaki Nakanishi, Shinji Kimura
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 一般社団法人電子情報通信学会 E89-A (12) 3427 - 3434 0916-8508 2006/12 [Refereed][Not invited]
     
    High-level synthesis is a novel method to generate a RT-level hardware description automatically from a high-level language such as C, and is used at recent digital circuit design. Floating-point to fixed-point conversion with bit-length optimization is one of the key issues for the area and speed optimization in high-level synthesis. However, the conversion task is a rather tedious work for designers. This paper introduces automatic bit-length optimization method on floating-point to fixed-point conversion for high-level synthesis. The method estimates computational errors statistically, and formalizes an optimization problem as a non-linear problem. The application of NLP technique improves the balancing between computational accuracy and total hardware cost. Various constraints such as unit sharing, maximum bit-length of function units can be modeled easily, too. Experimental result shows that our method is fast compared with typical one, and reduces the hardware area.
  • Takashi Horiyama, Kazuo Iwama, Jun Kawahara
    In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006) 4288 71 - 80 2006/12 [Refereed][Not invited]
  • Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Hirotaka Ono, Toshinori Sakuma, Masafumi Yamashita
    DISCRETE APPLIED MATHEMATICS 154 (16) 2247 - 2262 0166-218X 2006/11 [Refereed][Not invited]
     
    In this paper, we study how to collect n balls moving with a fixed constant velocity in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls; (ii) maximizing the number of the balls collected by k robots; (iii) minimizing the number of the robots to collect all n balls. The situations considered in this paper contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability-intractability frontier in the ball collecting problems in the Euclidean plane. (c) 2006 Published by Elsevier B.V.
  • Youichi Hanatani, Takashi Horiyama, Kazuo Iwama
    Discrete Applied Mathematics 154 (16) 2263 - 2270 0166-218X 2006/11/01 [Refereed][Not invited]
     
    The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is "easier" than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2n, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. © 2006 Elsevier B.V. All rights reserved.
  • An Optimization Method in Floating-point to Fixed-point Conversion using Positive and Negative Error Analysis and Sharing of Operations
    N. Doi, T. Horiyama, M. Nakanishi, S. Kimura
    Proc. of the 12th Workshop on Synthesis And System Integration of Mixed Information technologies(SASIMI 2004) 466 - 471 2004/10 [Refereed][Not invited]
  • T Horiyama, T Ibaraki
    DISCRETE APPLIED MATHEMATICS 142 (1-3) 151 - 163 0166-218X 2004/08 [Refereed][Not invited]
     
    We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram, for two cases of general and Horn knowledge-bases. Our main results say that both finding a model of a knowledge-base and deducing from a knowledge-base can be done in linear time for a general knowledge-base, but that abduction is NP-complete even for a Horn knowledge-base. Then, we consider abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases are also discussed. (C) 2004 Elsevier B.V. All rights reserved.
  • Yuichi Asahiro, Takashi Horiyama, Kazuhisa Makino, Hirotaka Ono, Toshinori Sakuma, Masafumi Yamashita
    Electronic Notes in Theoretical Computer Science 91 229 - 245 1571-0661 2004/02/16 [Refereed][Not invited]
     
    In this paper, we study how to collect n balls moving with constant velocities in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-Target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls, (ii) maximizing the number of the balls collected by k robots, and (iii) minimizing the number of the robots to collect all n balls. The situations considered here contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability- intractability frontier in the ball collecting problems in the Euclidean plane. © 2004 Elsevier B.V. All rights reserved.
  • Youichi Hanatani, Takashi Horiyama, Kazuo Iwama
    Proc. of the 6th International Conference on Theory and Application of Satisfiability Testing, Lecture Notes in Computer Science 2919 69 - 77 0302-9743 2004 [Refereed][Not invited]
     
    The following problem is considered: Given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is "easier" than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments) / 2(n), where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem axe presented: One is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms. This is a preliminary report of the on-going research.
  • N. Doi, T. Horiyama, M. Nakanishi, S. Kimura
    In. Proc. of Asia and South Pacific Design Automation Conference 2004 (ASP-DAC 2004) 80 - 85 2004/01 [Refereed][Not invited]
  • N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, K. Watanabe
    IEICE Trans. Fundamentals 一般社団法人電子情報通信学会 E86-A (12) 3184 - 3191 0916-8508 2003/12 [Refereed][Not invited]
     
    In the hardware synthesis from a high-level language such as C, the bit length of variables is one of the key issues for the area and speed optimization. Usually, designers are required to optimize the bit-length of each variable manually using the time-consuming simulation on huge-data. In this paper, we propose an optimization method of the fractional bit length in the conversion from floating-point variables to fixed-point variables. The method is based on error propagation and the backward propagation of the accuracy limitation. The method is fully analytical and fast compared to simulation based methods.
  • E Boros, T Horiyama, T Ibaraki, K Makino, M Yagiura
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 39 (3) 223 - 257 1012-2443 2003/11 [Refereed][Not invited]
     
    We consider data sets that consist of n-dimensional binary vectors representing positive and negative examples for some ( possibly unknown) phenomenon. A subset S of the attributes ( or variables) of such a data set is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we study the problem of finding small support sets, a frequently arising task in various fields, including knowledge discovery, data mining, learning theory, logical analysis of data, etc. We study the distribution of support sets in randomly generated data, and discuss why finding small support sets is important. We propose several measures of separation ( real valued set functions over the subsets of attributes), formulate optimization models for finding the smallest subsets maximizing these measures, and devise efficient heuristic algorithms to solve these ( typically NP-hard) optimization problems. We prove that several of the proposed heuristics have a guaranteed constant approximation ratio, and we report on computational experience comparing these heuristics with some others from the literature both on randomly generated and on real world data sets.
  • N. Doi, T. Horiyama, M. Nakanishi, S. Kimura, K. Watanabe
    Proc. of 12th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI2003) 129 - 136 2003/04 [Refereed][Not invited]
  • Takashi Horiyama, Toshihide Ibaraki
    Information Processing Letters 85 (4) 191 - 198 0020-0190 2003/02 [Refereed][Not invited]
     
    We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their Horn CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results hold on any class of functions having a basis of polynomial size. (C) 2002 Elsevier Science B.V. All rights reserved.
  • An On-Chip High Speed Serial Communication Method Based on Independent Ring Oscillators
    S. Kimura, T. Hayakawa, T. Horiyama, M. Nakanishi, K. Watanabe
    Proc. of International Solid-State Circuits Conference (ISSCC2003) 390 - 391 2003/02 [Refereed][Not invited]
  • S Kimura, A Ishii, T Horiyama, M Nakanishi, H Kajihara, K Watanabe
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E85A (12) 2701 - 2707 0916-8508 2002/12 [Refereed][Not invited]
     
    The paper describes the folding method of logic functions to reduce the size of memories to keep the functions. The folding is based on the relation of fractions of logic functions. If the logic function includes 2 or 3 same parts, then only one part should be kept and other parts can be omitted. We show that the logic function of I-bit addition can be reduced to half size using the bit-wise NOT relation and the bit-wise OR relation. The paper also introduces 3-1 LUT's with the folding mechanism. A full adder can be implemented using only one 3-1 LUT with the folding. Multi-bit AND and OR operations can be mapped to our LUT's not using the extra cascading circuit but using the carry circuit for addition. We have also tested the mapping capability of 4 input functions to our 3-1 LUT's with folding and carry propagation mechanisms. We have shown the reduction of the area consumption when using our LUT's compared to the case using 4-1 LUT's on several benchmark circuits.
  • S. Kimura, T. Horiyama, M. Nakanishi, H. Kajihara
    Proc. of International Conference on Computer Aided Design (ICCAD2002) 694 - 698 2002/11 [Refereed][Not invited]
  • Takashi Horiyama, Toshihide Ibaraki
    Artificial Intelligence 136 (2) 189 - 213 0004-3702 2002/04 [Refereed][Not invited]
     
    We consider the use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases, and show that, from the view point of space requirement, the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations. We then present polynomial time algorithms for the two problems of testing whether a given OBDD represents a unate Boolean function, and of testing whether it represents a Horn function. (C) 2002 Published by Elsevier Science B.V.
  • Takashi Horiyama, Toshihide Ibaraki
    Proc. of the 12th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 2223 231 - 243 0302-9743 2001/12 [Refereed][Not invited]
     
    We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results holds on any class of functions having a basis B with \B\ = d.
  • Speech Recognition Chip for Monosyllables
    Kazuhiro Nakamura, Qiang Zhu, Shinji Maruoka, Takashi Horiyama, Shinji Kimura, Katsumasa Watanabe
    Proc. of the 6th Asia and South Pacific Design Automation Conference 396 - 399 2001/01 [Refereed]
  • A Real-time 64-Monosyllable Recognition LSI with Learning Mechanism
    Kazuhiro Nakamura, Qiang Zhu, Shinji Maruoka, Takashi Horiyama, Shinji Kimura, Katsumasa Watanabe
    Proc. of the 6th Asia and South Pacific Design Automation Conference 31 - 32 2001/01 [Refereed]
  • Takashi Horiyama, Toshihide Ibaraki
    Proc. of the 11th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 1969 120 - 131 0302-9743 2000/12 [Refereed][Not invited]
     
    We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram (OBDD), for two special cases of general and Horn knowledge-bases. Our main results say that both finding a, model of a knowledge-base and deducing from a knowledge-base. can be done in linear time for general case, but that abduction is NP-complete even if the knowledge-base is restricted to be Horn. Then, we consider the abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases axe also discussed.
  • New Graph Calculi for Planar Non-3-Colorable Graphs,
    Youichi Hanatani, Takashi Horiyama, Kazuo Iwama, Suguru Tamaki
    IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences E91-A (9) 2301 - 2307 2000/09 [Refereed]
  • Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Mutsunori Yagiura
    Proc. of the 2nd International Conference on Intelligent Data Engineering and Automated Learning, Lecture Notes in Computer Science 1983 133 - 138 2000 [Refereed]
  • Takashi Horiyama, Toshihide Ibaraki
    Proc. of the 10th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 1741 83 - 92 0302-9743 2000 [Refereed][Not invited]
     
    We propose to make use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases. We show that the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations in the sense of space requirement. We then consider two recognition problems of OBDDs, and present polynomial time algorithms for testing whether a given OBDD represents a unate Boolean function, and whether it represents a Horn function.
  • Naofumi Takagi, Takashi Horiyama
    IEEE Transactions on Computers 48 (1) 76 - 80 1999 [Refereed][Not invited]
  • Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
    Takashi Horiyama, Shuzo Yajima
    IEICE Trans. Inf. & Syst E81-D (8) 793 - 800 1998/08 [Refereed]
  • Takashi Horiyama, Shuzo Yajima
    Proc. of the 8th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 1350 163 - 172 1997 [Refereed]

MISC

  • Enumeration of Non-isomorphic Unordered Trees with Degree Sequence Constraints
    Shuhei Denzumi, Takashi Horiyama, Kazuhiro Kurita, Atsuki Nagao, Kazuhisa Seto, Kunihiro Wasa  情報処理学 会, アルゴリズム研究会  192-  (11)  1  -6  2023/05  [Not refereed]
  • ZDD を用いた最適円 筒あみだくじの列挙
    岩崎善泰, 堀山貴史, 松井泰子, 野崎雄太, 脊戸和寿, 山中克久  情報処理学会, アルゴリズム研究会  192-  (3)  1  -8  2023/03
  • あみだくじと菱形タイリングの列挙
    堀山貴史  科学研究費補助金学術 変革領域(B) 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチ の融合, 第34 回セミナー  2023/01  [Invited]
  • 自己同型写像の断片を用いた代表元の反復抽出によ る同型性の除去
    高橋孔平, 脊戸和寿, 堀山貴史  電子情報通信学会技術研究報告  122-  (294)  51  -58  2022/12
  • 最小重み Laman グラフの総交点数と厚みの下界の改良
    河上悠輝, 高橋駿, 脊戸和寿, 堀山貴史, 小林祐貴, 東川雄哉, 加藤直樹  第35 回回路とシステムワークショッ プ  191  -196  2022/08
  • 文字列中の異なる閉文字列の数え上げと 最大個数について
    高橋駿, 脊戸和寿, 堀山貴史, 三重野琢也  夏のLAシンポジウム  2022/07
  • 区間最長回文クエリに対する時間最適 アルゴリズム
    三谷和暉, 脊戸和寿, 堀山貴史, 三重野琢也  夏のLAシンポジウム  2.1-  (2.8)  2022/07
  • 最小重み Laman グラフの総交点数と厚みの下界の改良
    河上悠輝, 高橋駿, 脊戸和寿, 堀山貴史, 小林祐貴, 東川雄哉, 加藤直樹  夏のLAシンポジウム  4.1  -4.7  2022/07
  • 複数の多面体の共通の展開図について
    堀山貴史  科学研究費補助金学術 変革領域(A) 社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化, AFSA コロキウム  2022/07  [Invited]
  • 正四面体の測地線折り
    西本清里, 堀山貴史, 舘知宏  第32 回折り紙の科学・数学・ 教育研究集会  2022/06
  • Solving Rep-tile by Computers
    Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda  14th Gathering 4 Gardner Conference  2022/04
  • レプ・タイルの定式化を用いた各種ソルバの性能比較
    番原睦則, 橋本健二, 堀山貴史, 湊真一, 中村駆, 西野正彬, 酒井正彦, 上原隆平, 宇野, 裕之, 安田宜仁  第16 回組合せ ゲーム・パズル研究集会  2022/03
  • ZDD の区間メモ化探索 技法によるコスト制約組合せ問題の高速な解列挙
    湊真一, 番原睦則, 堀山貴史, 川原純, 瀧川一学, 山口勇太郎  情報処理学会, アルゴリズム研究会  1  -8  2022/03
  • 45度系格子パターンにおける局 所平坦折り可能な展開図の数え上げとZDDによる列挙
    榎本優大, 河上悠輝, 脊戸和寿, 堀山貴史, 三谷純  冬のLAシンポジウム  6.1  -6.12  2022/02
  • フィボナッチ文字列の最小文法は RePair 文法
    三重野琢也, 稲永俊介, 堀山貴史  冬のLAシンポジウム  20.1  -20.3  2022/02
  • あみだくじと菱形タイリングの列挙
    堀山貴史  人工知能学会, 第119 回 人工知能基本問題研究会  1  2022/01  [Invited]
  • Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi 0005  CoRR  abs/2201.08118-  2022/01
  • ポリオミノ と格子凸多角形による多層タイル張り
    千田皐汰, Erik Demaine, Martin Demaine, David Eppstein, Adam Hesterberg, 堀山貴史, John Iacono, 伊藤大雄, Stefan Langerman, 上原隆平, 宇野裕之  電子情報通信学会技術研究報告  121-  (218)  11  -18  2021/10
  • Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Shin-ichi Minato, Kakeru Nakamura, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, Norihito Yasuda  CoRR  abs/2110.05184-  2021/10
  • ZDD による45 度系格子パターンにおける局 所平坦折り可能な展開図の列挙
    榎本優大, 脊戸和寿, 堀山貴史, 三谷純  第29 回折り紙の科学・数学・教育研究集会  2021/06
  • 動的計画法に基づくSimple Polygonization 列挙アルゴリズムの実験的評価
    中畑裕, 堀山貴史, 湊真一, 山中克久  情報処理学会, アルゴリズム研究会  1-  (8)  2021/03
  • コスト制約つき組合せ問題に対するZDDを用いた高速な解列挙手法
    湊真一, 番原睦則, 堀山貴史, 川原純, 瀧川一学, 山口勇太郎  電子情報通信学会技術研究報告  120-  (276)  8  -15  2020/12
  • 覆面算を列挙するオートマトンの効率的な構築手法
    渡部航也, ヘンリアンディプタラマ, 吉仲亮, 堀山貴史, 篠原歩  電子情報通信学会技術研究報告,  120-  (276)  16  -23  2020/12
  • 正多面体の折り判定問題の多項式時間解法
    上原隆平, 門口あきら, 鎌田斗南, 堀山貴史  第29 回折り紙の科学・数学・教育研究集会  2020/12
  • Sorting by Five Prefix Reversals
    Tetsuya Araki, Takashi Horiyama, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka  情報処理学会, アルゴリズム研究会  1  -7  2020/09
  • Polyhedral Forms from Folding Geodesic Strips
    Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi  Virtual Technical Meeting of the Society of Engineering Science  2020/09
  • Yu Nakahata, Takashi Horiyama, Shin-ichi Minato, Katsuhisa Yamanaka  CoRR  abs/2001.08899-  2020/01  [Not refereed][Not invited]
  • Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato  CoRR  abs/1911.07465-  2019/11  [Not refereed][Not invited]
  • Enumeration with Isomorphism Elimination
    Takashi Horiyama  The 3rd International Workshop on Enumeration Problems & Applications  2019/10  [Invited]
  • Takashi Horiyama, Jun Kawahara, Shin-ichi Minato, Yu Nakahata  CoRR  abs/1904.09438-  2019  [Not refereed][Not invited]
  • YAMANAKA KATSUHISA, HORIYAMA TAKASHI, UNO TAKEAKI, WASA KUNIHIRO  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報  118-  (295)  1  -6  2018/11/12
  • YAMANAKA KATSUHISA, HORIYAMA TAKASHI, UNO TAKEAKI, WASA KUNIHIRO  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報  118-  (296)  1  -6  2018/11/12
  • NAKAHATA Yu, SUZUKI Hirofumi, ISHIHATA Masakazu, HORIYAMA Takashi  Proceedings of the Annual Conference of JSAI  JSAI2018-  4K1OS16a03  -4K1OS16a03  2018  
    有向非巡回グラフ(DAG)は計算機科学における基本的な構造である. 応用において,DAGをより小さなDAGに縮約する問題は,命令セット拡張問題等のために重要である. 本研究では,DAGが与えられたとき,いくつかの辺を選んで縮約した結果がDAGとなるような辺の選び方をすべて列挙するアルゴリズムを提案する. 提案手法はフロンティア法に基づき,所望の辺部分集合の族を表現するデータ構造ZDDを構築するアルゴリズムである.
  • 伝住周平, 堀山貴史, 栗田和宏, 中畑裕, 鈴木浩史, 和佐州洋, 山崎一明  電子情報通信学会技術研究報告  118-  (216(COMP2018 9-20)(Web))  2018
  • Horiyama Takashi, Ito Takehiro, Ono Hirotaka, Otachi Yota, Uehara Ryuhei, Uno Takeaki  数理解析研究所講究録  1799-  123  -129  2012/06
  • 小林 有, 堀山 貴史  数理解析研究所講究録  1799-  65  -66  2012/06
  • SUGIMOTO Takuma, HORIYAMA Takashi  IEICE technical report  110-  (232)  19  -25  2010/10/08  
    Vickrey auction, in which the highest bidder wins at the second highest price, is a well-known incentive compatible auction. For achieving the privacy of bidders, we can run the auction without revealing the bidding prices to bidders, while it allows the auctioneer to cheat the second highest bidding price. In this paper, we propose making use of the techniques of secret sharing, and design an information-theoretically secure protocol that prohibits auctioneers from cheating the bidders, and that does not leak any additional information against the set of size t
  • 堀山 貴史  日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集  2009-  80  -81  2009/09/09
  • HORIYAMA Takashi, HIGUCHI Kosuke  IEICE technical report  109-  (108)  17  -21  2009/06/22  
    The longest path problem is, given an undirected graph with non-negative integer weights for the edges, to find the simple path of the largest length. Although the shortest path problem has brilliant algorithms in the literature, the longest path has no efficient algorithms. In this paper, we treat the longest path problem, the s-t longest path problem, and the all pairs longest path problem. For these problems, we propose two types of algorithms based on the exhaustive search and the 0-1 integer programming. We also implement and evaluate the algorithms by the benchmark instances of the path selection in JR Urban areas.
  • HORIYAMA Takashi, SAMEJIMA Masato  RIMS Kokyuroku  1649-  55  -57  2009/05
  • Enumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search
    T. Horiyama, M. Samejima  Proc. of the 2nd Asian Association for Algorithms and Computation Annual Meeting  (to appear)-  2009  [Not refereed][Not invited]
  • Enumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search
    T. Horiyama, M. Samejima  Proc. of the 2nd Asian Association for Algorithms and Computation Annual Meeting  (to appear)-  2009  [Not refereed][Not invited]
  • CHEN Lei, HORIYAMA Takashi, NAKAMURA Yuichi, KIMURA Shinji  IEICE technical report  108-  (23)  19  -24  2008/05/09  
    Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method, sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay.
  • CHEN Lei, HORIYAMA Takashi, NAKAMURA Yuichi, KIMURA Shinji  情報処理学会研究報告システムLSI設計技術(SLDM)  2008-  (38)  55  -60  2008/05/01  
    Leakage power dissipation of logic gates has become an increasingly important problem. A novel fine-grained power gating approach based on the controlling value of logic gates is proposed for leakage power reduction. In the method, sleep signals of the power-gated blocks are extracted based on the probability of the controlling value of logic gates without any extra control logic. A basic algorithm and a probability-based heuristic algorithm have been developed to implement this method. The steady maximum delay constraint has also been introduced to handle the delay overhead. Experiments on the ISCAS'85 benchmarks show the effectiveness of our algorithms and the effect on the extra delay.
  • Density Condensation of Boolean Formulas Based on Covering Codes
    T. Horiyama, A. Sato  Proc. of the 1st Asian Association for Algorithms and Computation Annual Meeting  1-  28  2008  [Not refereed][Not invited]
  • HANATANI Yoichi, HORIYAMA Takashi, IWAMA Kazuo, TAMAKI Suguru  IEICE technical report  107-  (219)  43  -50  2007/09/13  
    The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calculus is polynomially bounded.
  • Truthful Auctions with Limited Range of Bids
    T. Horiyama, K. Iwama, D. Sumita  Proc. of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications  5-  53  -61  2007  [Not refereed][Not invited]
  • ANNO Takafumi, HORIYAMA Takashi, IWAMA Kazuo  RIMS Kokyuroku  1489-  188  -194  2006/05
  • DOI Nobuhiro, HORIYAMA Takashi, NAKANISHI Masaki, KIMURA Shinji  情報処理学会研究報告システムLSI設計技術(SLDM)  2005-  (27)  133  -138  2005/03/18  
    This paper presents bit-length optimization technique for high-level synthesis based on non-linear programming and searching integer solutions. The results of the bit-length optimization based on non-linear programming are real values, and these values are converted to integer with round-up for hardware implementation. In this paper, we show a method to search integer solutions under the constraints of the real solution. The experimental results shows the advantage of searching based method.
  • DOI Nobuhiro, HORIYAMA Takashi, NAKANISHI Masaki, KIMURA Shinji  IEICE technical report. Computer systems  104-  (738)  43  -48  2005/03/11  
    This paper presents bit-length optimization technique for high-level synthesis based on non-linear programming and searching integer solutions. The results of the bit-length optimization based on non-linear programming are real values, and these values are converted to integer with round-up for hardware implementation. In this paper, we show a method to search integer solutions under the constraints of the real solution. The experimental results shows the advantage of searching based method.
  • DOI Nobuhiro, HORIYAMA Takashi, NAKANISHI Masaki, KIMURA Shinji  情報処理学会研究報告システムLSI設計技術(SLDM)  2004-  (56)  41  -46  2004/05/28  
    Various optimization techniques such as bit-length optimization are required for hardware generation from C programs. The value range analysis and dataflow analysis are effective for such optimization and static program analysis methods have been used. The static methods, however, have several problems such as the preciseness, the overestimation, etc. In this paper, we describe a program analysis method based on abstract interpretation and its application for datapath optimization.
  • Masanishi Shingo, Horiyama Takashi, Iwama Kazuo  RIMS Kokyuroku  1375-  68  -77  2004/05
  • Sakuma Toshinori, Ono Hirotaka, Yamashita Masafumi, Asahiro Yuichi, Makino Kazuhisa, Horiyama Takashi  RIMS Kokyuroku  1325-  8  -14  2003/05
  • KAJIHARA Hirotsugu, NAKANISHI Masaki, HORIYAMA Takashi, KIMURA Shinji, WATANABE Katsumasa  情報処理学会研究報告システムLSI設計技術(SLDM)  2003-  (7)  37  -42  2003/01/28  
    The paper describes an area efficient FPGA architecture based on LUTs with logic function folding. Each LUT is a 3-1 LUT but is enhanced to implement a full adder function with only one LUT. The area of our 3-1 LUT is about 56 % compared to that of a simple 4-1 LUT. In the paper, we measure not only the LUT area but also the area of routing resource. We adopt the well-known island style-architecture for the routing mechanism, and find that the total FPGA area can be saved up to 32.4 % and on average 12 % by the experiments on several benchmark circuits compared to FPGA architecture based on 4-1 LUTs.
  • Ishii Atsushi, Kajihara Hirotsugu, Nakanishi Masaki, Horiyama Takashi, Kimura Shinji, Watanabe Katsumasa  Proceedings of the IEICE General Conference  2002-  104  -104  2002/03/07
  • Horiyama Takashi, Ibaraki Toshihide  RIMS Kokyuroku  1148-  175  -180  2000/04
  • Horiyama Takashi, Ibaraki Toshihide  RIMS Kokyuroku  1093-  93  -98  1999/04
  • 堀山 貴史, 矢島 脩三  全国大会講演論文集  53-  175  -176  1996/09/04  
    The size of an OBDD largely depends on the variable ordering. It is important to clarify the lower bounds of OBDDs representing arithmetic functions. In this report, we investigate a lower bound of the size of OBDDs representing integer division. More precisely, we focus on each bit of the output of the n-bit / n-bit division, and prove that the size of OBDDs representing the i-th bit is Ω(2^<(n-2)/8>). We also prove the same lower bound on ∨V-OBDDs, ∧-OBDDs and ⊕ -OBDDs. To prove this lower bound, we introduce a strong fooling set, which has a more restricted property than a fooling set.

Association Memberships

  • European Association for Theoretical Computer Science (EATCS)   電子情報通信学会   情報処理学会   LAシンポジウム   

Research Projects

  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research
    Date (from‐to) : 2023/04 -2028/03 
    Author : 久保山 哲二, 草場 彰, 堀山 貴史, 宇野 毅明, 平田 耕一
  • 日本学術振興会:科学研究費助成事業
    Date (from‐to) : 2024/04 -2027/03 
    Author : 東川 雄哉, 加藤 直樹, 照山 順一, 堀山 貴史, Sljoka Adnan, 安田 修悟, 小林 祐貴
  • 日本学術振興会:科学研究費助成事業
    Date (from‐to) : 2023/04 -2027/03 
    Author : 東川 雄哉, 加藤 直樹, 照山 順一, 堀山 貴史, Sljoka Adnan, 安田 修悟, 小林 祐貴
  • 日本学術振興会:科学研究費助成事業
    Date (from‐to) : 2023/06 -2026/03 
    Author : 松永 康佑, 舘 知宏, 堀山 貴史
  • 日本学術振興会:科学研究費助成事業 基盤研究(B)
    Date (from‐to) : 2022/04 -2026/03 
    Author : 堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 2022/04 -2025/03 
    Author : 繁富 香織, 上原 隆平, 堀山 貴史
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (A)
    Date (from‐to) : 2020/11 -2025/03 
    Author : 湊 真一, 宇野 毅明, 安田 宜仁, 堀山 貴史, 河原林 健一, 山下 茂, 牧野 和久, 上原 隆平, 瀧本 英二, 玉置 卓
     
    2020年度の4か月間は、研究領域全体の組織立ち上げ準備の期間として位置づけ、本研究領域の目標や活動の方向性に関する参加メンバの意識合わせ、階層的な組織構成の整備と定例会議体制の設定、メーリングリストやSNS等による内部連絡体制・文書共有システムの整備、研究領域のwebサイトの立ち上げと広報資料の作成、連携拠点オフィスの確保と必要な什器や機材の整備、事務系/技術系スタッフの必要人数の精査と採用、研究領域全体で利用する大型計算サーバなどの共用設備の精査と購入計画の策定実施、十分な応募件数の公募班を集めるための広報活動と審査体制の整備、本研究領域の外部評価者の人選と依頼、等の共通的な業務を実施した。 2020年度の研究領域全体に関わるイベントとしては、全ての計画班の代表者・分担者を対象とした「内部向けキックオフ領域集会」を12月9日に開催したこと、および本研究領域に関心を持つ可能性がある全ての研究者を対象として対外向けの「スタートアップシンポジウム」を1月7日に開催した他、新設した京都寺町三条サテライトラボや既存の東京神田サテライトラボと各研究者が所属する研究機関をリモートで接続する体制を整え、小規模な研究打合せや運営会議を必要に応じて随時実施した。これらの活動実績により本研究領域全体の情報交換を円滑に行う体制が整いつつある。 以上の活動は、新型コロナの感染状況に応じて、対面と遠隔を適切に組合わせながら実施した。
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (A)
    Date (from‐to) : 2020/11 -2025/03 
    Author : 堀山 貴史, 湊 真一, 上原 隆平, 宇野 裕之, 竹田 正幸, 番原 睦則, 松井 泰子
     
    情報化社会におけるデータの規模の拡大や組合せの複雑化などにより、理論と実用の両方の観点から、問題が内包する大規模離散構造を利用したアルゴリズムの設計技法が求められている。本研究では、これまで個別の分野において個々のアイデアに基づいて設計されてきたアルゴリズムの成功事例を理論計算機科学の観点から改めて観察することで、大規模離散構造を理解し、その構造をどのように利用しているかを整理する。このケースワークをもとに、指数関数的な壁に立ち向かうアルゴリズム設計のための方法論を新たに体系化することで、理論と実装が一体となって大規模離散構造処理のための革新的アルゴリズム基盤技術へと昇華することを目指している。このために、具体的には、二分決定グラフ (BDD; Binary Decision Diagram) やその亜種の零抑制型二分決定グラフ (ZDD; Zero-suppressed BDD) のアルゴリズム、逆探索による列挙アルゴリズム、グラフ探索アルゴリズム、文字列処理アルゴリズム、論理式の充足可能性判定問題 (SAT; satisfiability problem) の充足解探索アルゴリズムなどの、指数関数的に大きな解空間を持つ問題における場合分けや数え上げ、列挙、索引化などが必要とされる分野を対象に、ケースワークを始めた。ここには、計算量理論の観点から、解を求めるための計算複雑さだけでなく、遷移問題も視野に入れている。こうした取り組みとして、具体的には、たとえば、与えられた点集合に対して自己交差のない多角形を求める単純多角形化問題において、逆探索の観点からの列挙だけでなく、ZDD 構築に用いられるフロンティア法の設計技法に着想を得て、問題の解空間の構造を把握する試みなどがある。
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    Date (from‐to) : 2020/04 -2025/03 
    Author : 湊 真一, 堀山 貴史, 瀧川 一学, 川原 純, 番原 睦則, 山口 勇太郎
     
    本年度の研究実績の概要は以下の通りである。 (i) 列挙と最適化の統合的アルゴリズム技法の研究と体系化:グラフの最短路問題のように、組合せ問題のアイテムにコストが定義されているときに、コスト総和が所与の閾値以下となるような実行可能解を列挙することは、多くの実用的な応用を持つ汎用的で重要な問題である。このような一般的なコスト制約つき組合せ問題に対して、ZDDを用いて大量の解を高速に全列挙する手法を考案した。実験の結果、実用的な規模の例題に対して、数百万通りの解集合を表すZDDを1秒以内で構築することができた。本研究結果は研究代表者自らが筆頭著者として国内研究会で発表し、今後、国際会議または論文誌での発表を目指して準備を進めている。 (ii) 離散構造処理系の基盤アルゴリズムの実装とソフトウェアの整備:BDD/ZDDをベースとする離散構造処理系のアルゴリズムは、原則として「BDDパッケージ」と呼ばれるソフトウェアライブラリとして公開されている。今年度に開発した高速列挙アルゴリズムの実装もこのパッケージに追加し、整備を進めている。 (iii) 関連分野との連携および応用分野への発展:ERATOや基盤(S)プロジェクトで形成された研究者コミュニティを可能な範囲で維持し、研究者が集まり最新の技術情報を交換する「場」を確保することを目的として、2020年9月17日に「基盤(A) プロジェクト近況報告&自由討論会」と呼ぶオンラインワークショップを企画した。最終的に48名の研究者が参加して活発な討論が行われ、研究者コミュニティの活性化に貢献した。
  • 日本学術振興会:科学研究費助成事業 挑戦的研究(萌芽)
    Date (from‐to) : 2020/07 -2023/03 
    Author : 松永 康佑, 舘 知宏, 堀山 貴史
     
    本研究はウイルス外殻の構造について、Casper and Klugの準等価理論による展開図を近似して正二十面体を作るアプローチとは対照的に、そもそも球面上を敷き詰めることのできる部品構造(コートタンパク構造)のパターンは何か?というタイリングの観点からウイルス外殻を調べ、外殻構造の構成とデザイン原理の理解を深化させることを目的とする。去年度は球面上のタイリングについて考察し、平面を埋め尽くすためのタイリング理論でわかっている部品構造の対象軸のうち6回対称軸を5回対称軸とみなすことで正二十面体のタイリングへと近似することを考案した。これを用いて準等価理論でT1に分類される外殻構造を観察したところ、外見上は4つの異なるタイリングへ分類できることがわかった。本年度は、去年度に主に外見だけで行ったT1外殻構造のタイリング分類を更に定量化するための研究を行った。まず一つ目に、外殻を構成するコートタンパク質モノマーの不斉炭素原子のデカルト座標を点群として発生させ、去年考案した正二十面体のタイリングを満たす平面を点群へフィッティングし分類するプログラムを開発した。実際に、T1外殻構造の一つのテストデータを定量的に分類できるようになった。二つ目として、剛体ドッキングプログラムを用いてコートタンパクのホモ二量体のドッキング計算を行い、得られたドッキングスコアとホモ二量体のスクリュー軸の関係を調べた。あるT1外殻構造では、スクリュー軸が3回対称軸と2回対称軸となるホモ二量体構造のスコアの成績が良かった一方で、別のT1外殻構造では5回対称軸と2回対称軸の成績が良かった。これは考案したタイリング分類の傾向と一致しており、タイリング分類が単なる見た目の分類だけでなく、構造の安定性とも関わっていることが示唆された。
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Challenging Research (Pioneering)
    Date (from‐to) : 2020/04 -2022/03 
    Author : Uehara Ryuhei
     
    The purpose of this research was to construct a theoretical model for the construction of the three-dimensional structure of small-sized cells through experiments using actual cell origami, and to evaluate the foldability for cells. Under some conditions, cell folding experiments were performed. Based on these experimental results, we devised some model candidates that give a valid "foldability index" considering physical constraints. We are currently verifying the validity between the experimental data and the theoretical model we devised, and are preparing to publish it as a paper in the future. Especially from the mathematical aspect, it is considered that the greatest significance of this research is that we were able to construct a theoretical model that incorporates physical constraints to some extent.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
    Date (from‐to) : 2018/04 -2021/03 
    Author : Horiyama Takashi
     
    We focused on the isomorphism, which appears in various problems of computational geometry. We developed isomorphism-elimination algorithms for enumerating geometric objects, and applied the methodology to various fields. The enumeration by our proposed algorithms are based on BDDs (Binary Decision Diagrams) and ZDDs (Zero-suppressed BDDs). By combining the algorithms with the enumeration algorithms with the frontier-method, which is the framework for constructing BDDs/ZDDs in the top-down manner, the enumeration achieves extremely fast speed and extremely small memory consumption. For example, experimental results show that the proposed method is more than 300 times faster and 3,000 times less memory than the conventional algorithm with only the frontier-method.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    Date (from‐to) : 2016/04 -2021/03 
    Author : Takeshi Koshiba
     
    The computational power of the DQC1 model, which is a formalization of non-universal quantum computation with initialization-hard quantum states, is shown to be superior to classical computation. Many quantum distributed algorithms are developed. Under the standard model for distributed algorithms, efficient quantum protocols for several fundamental problems such as the shortest path problem. Secure quantum delegated computation cannot achieve the perfect security for classical clients. By introducing the notion of rewards in quantum computations, classical verification of having the quantum power of the server is affirmatively settled. This is a game-theoretic solution and gives a novel method in quantum computation.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (S)
    Date (from‐to) : 2015/05 -2020/03 
    Author : MINATO Shin-ichi
     
    In this project, we aimed to construct the core algorithms for discrete structure manipulation systems, and to provide efficient software tools for many researchers in various application areas. Our achievements include that (1) we first succeeded in enumerating all connected sub-block patterns (in total 109.8 billion patterns) of 47 prefectures in Japan, the data is open for all Japanese citizens from the governmental statistics center, and (2) we produced many academic papers, accepted at the top-conferences such as AAAI, WWW, KDD, INFOCOM, AISTATS, SDM, etc.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 2015/07 -2019/03 
    Author : Jin-ichi Itoh
     
    We got results balanced well as follows for (A) continuous folding of polyhedron, (B) cooperation with architectural engineering, (C) cooperation with mathematical education, (D) establishment of intuitive geometry. (A) We discovered some new continuous flat folding of polyhedra and extent it the union of 2D surfaces of high dimensional several regular polytopes. (B) It was shown to change Coxeter's regular skew polyhedra to have rigidity. (C) Several meeting on mathematics education was held to demonstrate the usefulness of intuitive geometry, and to develop teaching materials using dynamic geometry software. (D) The meeting "intuitive geometry" was continued, and the recognition of the name "intuitive geometry" could be improved. In addition, We have advanced several research that can be called intuitive geometry.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
    Date (from‐to) : 2015/04 -2018/03 
    Author : Horiyama Takashi
     
    The methodology for designing enumeration algorithms of geometric objects are discussed by integrating basic technologies (e.g., BDDs (Binary Decision Diagrams), ZDDs (Zero-suppressed BDDs) and reverse search). We also applied the methodology to various fields. First, we focused on enumerating the developments of orthogonal boxes. We introduced the notion of unit square development, and proposed an efficient algorithms for constructing ZDDs of the unit square developments. We also considered the problem from the reverse side. That is, we proposed algorithms checking whether a given orthogonal polygon can be folded into an orthogonal box (and giving the creases if possible). As for the application of our method, we have enumerated all patterns of partitions for elections within a disparity bound, and also all rhombille tilings.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
    Date (from‐to) : 2012/06 -2017/03 
    Author : Watanabe Osamu, ASANO Takao, IBARAKI Toshihide, IMAI Hiroshi, TODA Seinosuke, MARUOKA Akira, MINATO Shinichi, MAKINO Kazuhisa, KAWARABAYASHI Kazuhisa, ASANO Tetsuo, KATOH Naoki, AVIS David, TOKUYAMA Takeshi, YAMASHITA Shigeru, TAKIMOTO Eiji, HORIYAMA Takashi, MORI Ryuhei
     
    The purpose of this project is to manage, as a headquarter, the whole research project for exploring the limits of computation (in short, the ELC project). Deepening the understanding of computation is a key for developing yet stronger and new methods of using computation, and for this purpose, the ELC project investigates the limits of computation from various view points from a wide area of mathematical science. For obtaining significant advancements by such a multi-disciplinary approach, the collaboration of researchers in the world is necessary. The main task of this project is to prepare an appropriate environment for promoting such collaborations. For this, we invited many researchers, organized a good number of research workshops, and organized several international symposiums from small to large. We also organized tutorial seminars, fall schools, and group study sessions for promoting our research and fostering young researchers.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
    Date (from‐to) : 2012/06 -2017/03 
    Author : Tokuyama Takeshi, SADAKANE Kunihiko, YAMANAKA Katsuhisa
     
    Our project aimed at development of several new methodologies on innovative data structures for big-data analysis utilizing the methodologies proposed and developed in the ELC project. The major accomplishments are: 1. Development of compressed data structures with efficient search and update algorithms 2. Solutions of problems in the application areas of genome and social big-data analysis by using theoretical compressed data structures, 3. Development of several algorithms and methods on ZDD and its application to structure enumeration in geometry and chemistry, and 4. Development of new data clustering method named data polishing with applications. Those accomplishments leads to real applications and succeed to several new influential data analysis projects lead by members of the project.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    Date (from‐to) : 2013/04 -2016/03 
    Author : IWAMA KAZUO, AVIS David, MIYAZAKI Shuichi, TAMAKI Suguru, ITO Hiro, HORIYAMA Takashi, YOSHIDA Yuichi, OKAMOTO Kazuya, SETO Kazuhisa, KAWAHARA JUN
     
    One of the main challenge in modern algorithm design is to cope with insufficient information. In this study, we try to construct a general framework for design of approximation algorithms that can cope with insufficient information due to rapidly growing data size. As a result, we give design and analysis of such algorithms for various problems in several fields such as graph problems, algorithmic game theory and randomized computation theory.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
    Date (from‐to) : 2012/04 -2015/03 
    Author : HORIYAMA Takashi
     
    The methodology for designing enumeration algorithms of geometric objects are discussed by integrating basic technologies (e.g., BDDs (Binary Decision Diagrams), ZDDs (Zero-suppressed BDDs) and reverse search). As for the enumeration of developments of polyhedra, the efficiency of the combined method with the frontier-based ZDD construction and a removal of isomorphic developments is shown. The extension of this method is discussed for enumerating general developments (i.e., developments obtained by cutting not only the edges but also faces) of polyhedra. Moreover, the counting method for essentially different developments of any polyhedron is proposed. We can count the number of non-isomorphic developments without enumerating the developments.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    Date (from‐to) : 2010 -2012 
    Author : IWAMA Kazuo, AVIS David, MIYAZAKI Shuichi, TAMAKI Suguru, ITO Hiro, KATOH Naoki, TOKUYAMA Takeshi, YAMASHITA Masafumi, WATANABE Osamu, HORIYAMA Takashi, KAWAHARA Jun, MORIZUMI Hiroki
     
    One of the main challenge in modern algorithm design is to copewith insufficient information. In this study, we try to construct a general framework fordesign and evaluation of algorithms that can cope with insufficient spatial information. Asa result, we give design and analysis of such algorithms for various problems in severalfields such as graph problems, algorithmic game theory and randomized computationtheory.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B)
    Date (from‐to) : 2008 -2010 
    Author : HORIYAMA Takashi
     
    This research project has the following three main results. (1) We have designed algorithms for enumerating Tsume-Shogi by the reverse method. As a result, we can prove the longest mating-moves for a given set of Shogi-pieces. (2) We have designed algorithms for generating fundamental domains of p4-tiling (i.e., the tiling by 4-fold rotation) and p6-tiling (i.e., the tiling by 6-fold rotation) based on the reverse search. (3) We have designed algorithms for enumerating the unfoldings of polyhedra. By enumerating all unfoldings and checking their overlapping, we have solved an open problem for hundreds of years : Is every edge-unfolding of Platonic solids nonoverlapping? The answer is yes!
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    Date (from‐to) : 2007 -2009 
    Author : IWAMA Kazuo, KATOH Naoki, ITO Hiro, MIYAZAKI Shuichi, TAMAKI Suguru, SUGIHARA Kokichi, TOKUYAMA Takeshi, YAMASHITA Masafumi, WATANABE Osamu, HORIYAMA Takashi
     
    One of the main challenge in modern algorithm design is to cope with insufficient information (to complement information). In this study, we rigorously discuss the desirable property of such algorithms and try to construct a framework for it including design techniques and evaluation method. As a result, we obtain efficient algorithms in various fields such as online, network, matching, randomized, geometric and distributed algorithms.
  • 日本学術振興会:科学研究費助成事業 若手研究(B)
    Date (from‐to) : 2005 -2007 
    Author : 堀山 貴史
     
    情報化社会の大規模化と多様化は、計算機による処理能力の向上と処理対象への柔軟な適応によるところが大きい。これは、コンピュータの処理速度の向上に顕著に見られるハードウェアの進歩に加えて、ソフトウェアのアルゴリズム革新に支えられている。ここに、アルゴリズムの設計と性能保証があらゆる分野の基礎として重視されてきている。アルゴリズムの性能保証には、理論的な性能解析が必要不可欠であるが、アルゴリズム設計と同じく人手で行っており、設計者の職人芸的なセンスに依存するところが大きい。本研究の主題は、アルゴリズムの理論的性能解析に計算機を援用することにある。これにより、定型的作業の負荷を減らし、思考の抽象度を高めることによる生産性の向上が期待できる。 本年度は、アルゴリズム的ゲーム理論の立場から、オークションのアルゴリズムの性能解析に関して検討を行った。具体的には、音楽ファイルなどの複製コストが無視できるほど小さく無限供給可能な商品に対する1ラウンド秘密入札オークションを対象とし、誘因両立性を持つアルゴリズムを設計した。また、入札の最高額と最低額の比rに関する競合比解析を提案し、本アルゴリズムの競合比がln r+1となることを示した。同様の観点から既存アルゴリズムの競合比をrの関数として解析し、小さなrに関しては提案アルゴリズムの競合比が常に良いことを示した。
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Priority Areas
    Date (from‐to) : 2004 -2007 
    Author : ITO Hiro, IWAMA Kazuo, MASUZAWA Toshimitsu, MIYAZAKI Shuichi, HORIYAMA Takashi
     
    グラフは接続関係を表現する抽象モデルとして有用であり, 古くから盛んに研究されている数学的対象である. 本特定領域研究では, ネットワークや計算機上での問題をグラフ問題としてモデル化し, そのアルゴリズム開発の研究を行った. その結果、密な部分グラフ発見問題, 供給点配置問題, 頂点被覆問題, 巡回セールスマン問題, 自己安定化問題, 安定マッチング問題などの様々な実用的問題について, 効率的なアルゴリズムを得ることができた.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 2004 -2006 
    Author : IWAMA Kazuo, ITO Hiro, MIYAZAKI Shuichi, HORIYAMA Takashi
     
    Traditionally the quality of discrete algorithms has been evaluated mostly by their asymptotic running time. However, it is often pointed out that running time is not a suitable measure of quality for some applications. Recently various measures have been proposed to evaluate algorithms in many perspectives. For example, "approximation ratio" is used to evaluate approximation algorithms, where an approximation algorithm must efficiently compute reasonable solutions for hard combinatorial problems. Another example, "competitive ratio" is used to evaluate online algorithms, where in online computation an algorithm must decide how to act on incoming items of information without any knowledge of future inputs. Both measures play very important roles in current algorithm theory. In our research, we think these new measures for algorithms as "quality for engineering" and develop high performance algorithms with respect to this quality. We mainly study network algorithms, matching algorithms and satisfiability algorithms. The followings are representative results of our project. There is an extension of stable matching problems, where ties and incomplete lists are allowed in preference lists. Finding maximum stable matchings in this setting is known to be NP-hard and (trivial) 2-approximation algorithm is also known. We show a 1.8-approximating algorithm for the problem, which first achieves the approximation ratio below 2 and improves the previous best ratio of 2-c/$\sqrt{n}$. It is an important open question whether minimum vertex cover problems (VC) are approximable within 2-ε and it is widely believed that the answer is in the negative. We consider VC on dense graphs and show a 2 /(1+A/d) approximation algorithm, which greatly improves the ratio 2 for general graphs. Here A, (d) is a maximum (average, resp.) degree of an input graph. The result is tight in the sense that if an improvement is possible, then we would have 2-approximation algorithms for general graphs.
  • 日本学術振興会:科学研究費助成事業 若手研究(B)
    Date (from‐to) : 2002 -2004 
    Author : 堀山 貴史
     
    情報化社会の発達にともない、クレジットカードや各種検査の結果などの多種多様なデータを、大量かつ容易に集めることができるようになってきている。このため、集められた膨大なデータからその傾向や規則性などの有用な情報を得ることを目的とした知識獲得の研究の重要性がさまざまな分野で指摘されている。本研究では、データと対応づけした論理関数を媒介として、データの持つ論理的内容を知識として抽出することを目指している。 今年度は、まず、二分決定グラフ(Ordered Binary Decision Diagrams)を知識表現の手段として用いた知識ベース処理について、計算複雑さに関する考察とアルゴリズム設計を行った。具体的には、OBDDを用いた手法では演繹(deduction)が任意の論理関数に対して線形時間で可能となることを示した。仮説推論(abduction)は任意の論理関数に対してはNP-hardとなるが、扱う関数をHorn関数に限定することで、仮説に任意のリテラルを取りえるような説明を求める多項式時間アルゴリズムを示した。また、証明システムの複雑さと密接に関連するHajos calculusに着目し、その平面グラフ版の問題について考察を行った。Hajos calculusは3彩色不能なグラフを生成する非決定性のプロセスである。本研究では、3彩色不能な平面グラフのみを生成できる生成則を2種類提案し、それぞれの規則の健全性と完全性を証明した。また、その規則間の多項式時間模倣性を示した。 また、自律学習機構を備えたハードウェアへの知識獲得手法の適用の基礎的な問題として、高位言語からハードウェア記述の自動合成を行う高位合成における、浮動小数点数のビット長最適化を扱った。誤差解析において正方向の誤差と負方向の誤差を独立して考慮し、また、非線形最適化ソルバーを利用してビット長最適化問題を解く手法を提案し、シミュレーションによる手法よりも良好な結果を得た。
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 2001 -2003 
    Author : IWAMA Kazuo, MIYAZAKI Shuichi, ITO Hiro, OKABE Yasuo, HORIYAMA Takashi
     
    Discrete algorithms have been evaluated by the unique measure 'asymptotic time complexity' for many cases. Recently, however, many other measures have been proposed, e.g., the approximation ratios for solving combinatorial problems approximately, and the competitive ratios for solving online problems in which we have no information on the future inputs. In this research, we studied these new measures as the criteria based on engineering requirements, and developed the methodologies for qualifying algorithms from this point of view. As to the stable marriage problems, it is known to be solvable in polynomial time. We have generalized the problem, and proved that it is also solvable in polynomial time even when ties in the lists or incomplete lists are allowed. While we proved the intractability for the case both ties and incompleteness are allowed, we proposed an approximation algorithm that achieves an approximation ratio less than 2. As to the satisfiability problems, we developed a 1.324^n algorithm for 3-SAT by complementarily combining two types of algorithms based on, the local search and the backtracking. We also considered condensing the density (i.e., the ratio of satisfying assignments to the 2^n assignments) of formulas. Other research topics are as follows ; online algorithms, network algorithms, quantum algorithms.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 2001 -2003 
    Author : IBARAKI Toshihide, HORIYAMA Takashi, NONOBE Koji, YAGIURA Mutsunori, HAJIME Ase
     
    Recently, problems encountered in real applications become more complicated and large-scaled. Among a wide variety of problem types, we focus on those problems whose core parts can be formulated as an optimization problem ; especially as a combinatorial (or discrete) optimization problem. Our goal is to develop a general-purpose problem solving system that can deal with combinatorial optimization problems. To achieve this, we have prepared a number of standard problems so that as many problems as possible can be written in one of their forms, and developed efficient, robust and flexible approximation algorithms, all of which are based on metaheuristics. Some of them are being used in practice, incorporated into production systems of companies. Our standard problems are listed below. ・CSP (Constraint Satisfaction Problem) ・MAXSAT (MAXimum SATisfiability problem) ・RCPSP (Resource Constrained Project Scheduling Problem) ・GAP (Generalized Assignment Problem), MRGAP (Multi-Resource GAP) ・SCP (Set Covering Problem) ・VRP (Vehicle Routing Problem) ・2PP (2-dimensional Packing Problem) ・1CSTP (1-dimensional Cutting STock Problem) ・2CSTP (2-dimensional Cutting STock Problem) ・FED (Feature Extraction from Data)
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 1999 -2001 
    Author : WATANABE Katsumasa, HORIYAMA Takashi, TAKAGI Kazuyosi, KIMURA Shinji, NAKANISHI Masaki
     
    The aim of our research is how to construct adaptable hardware and software for changing environment. In design and implementat ion of new informat ion systems, we research about methods of const ruct ing re-configurable system depending on changing envi ronment from total view points of hardware and software. Through 3 years, we studied at the fol lowing theoretical and practical aspects. (1) From the view point of adaptable software, we propose about the representat ion and construct ion of act ive software, the spontaneity and extensibility of objects in conversational programming, and optimizing C compiler to generate optimum bit-length variables in VHDL. Then we implement some examples and show the effectiveness of our proposals. (2) From the view point of adaptable hardware, as examples of LSI with re-configurability, we design and construct LSI of Java processor with abiliity to shorten the sequence of instructions dynamically, LSI to guess the eye track and LSI to determine the direct ion of face person-independently. These LSI have hardware oriented algorithms and give response in real time. (3) About hardware synthesis and verification, we propose a new symbolic image computation algorithm based on BDD(Binary Decision Diagram) constrain operator. Then we show good performance and effectiveness of the algorithm to large scale circuits. (4) From the view point of learning and knowledge acquirement for environmental adaptability, we propose a method based on OBDD(ordered BOD). Then we design the algorithms of mutual conversion between conventional character istic model and OBDD. (5) We pay attention to quantum computation. Quantun computers can exploi t quantum paralleiism to recognize the dynamic characteristics of environment. Then we research non-deterministic quantum fin te automata (OFA) and compare OFA with the classical counterparts. As results of the research, we get some mechanism for constructing systems with environmental adaptability in hardware and software totally.
  • Japan Society for the Promotion of Science:Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Priority Areas (B)
    Date (from‐to) : 1998 -2000 
    Author : IBARAKI Toshihide, NONOBE Koji, HORIYAMA Takashi, YAGIURA Mutsunori, SHINANO Yuji
     
    Recently, many types of metaheuristics based on local search, e. g., simulated annealing, genetic algorithm, and tabu search, have been proposed, and successfully applied to various combinatorial optimization problems. The objective of this research is to develop powerful general-purpose algorithms for combinatorial problems arising in real applications. To achieve this purpose, we developed metaheuristics algorithms for the following problems : (a) Weighted Constraint Satisfaction Problem, (b) Generalized Assignment Problem, (c) Resource Constrained Project Scheduling Problem, (d) Set Covering Problem, (e) Cutting Stock Problem, (f) Vehicle Routing Problem, (g) Rectangle Packing Problem, and others. These problems are representative combinatorial optimization problems, and their conventional formulations are rather simple. In our research, aiming at improving the applicability of algorithms, we extended these formulations so that more practical and complicated problems can be handled. In designing algorithms, we adopted iterated local search and tabu search as the frameworks, and defined search space and neighborhoods carefully so as to attain better performance. We also incorporated some mechanisms that adaptively control program parameters during the search, which can reduce users' efforts to tune the parameters appropriately. In computational experiments, we solved many benchmark instances, and succeeded to improve the best known values for many instances. As to practical problems, our codes could also find solutions of high quality in reasonable computational time. Some codes are already being used in practical applications.
  • -
  • -


Copyright © MEDIA FUSION Co.,Ltd. All rights reserved.