Search

Your search keyword '"Imahori, Shinji"' showing total 151 results
Start Over Author "Imahori, Shinji"
151 results on '"Imahori, Shinji"'

1. A 1+O(1/N) approximation algorithm for TTP(2)

Author

Imahori, Shinji

Subjects
Computer Science - Data Structures and Algorithms
Abstract

The traveling tournament problem is a well-known benchmark problem of the sports scheduling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive home games and that of consecutive away games are at most two (called TTP(2)). The approximation ratio of the proposed algorithm is 1 + 24/n for n teams, which is the first 1 + O(1/n) approximation algorithm for TTP(2)., Comment: 6 pages, Appeared in Proceedings of International Symposium on Scheduling 2015, pp.186-191 http://kaede.cs.kobe-u.ac.jp/iss2015/

Published
2021

2. Escherization with Generalized Distance Functions Focusing on Local Structural Similarity

Author

Nagata, Yuichi and Imahori, Shinji

Subjects
Computer Science - Computational Geometry
Abstract

The Escherization problem involves finding a closed figure that tiles the plane that is most similar to a given goal figure. In Koizumi and Sugihara's formulation of the Escherization problem, the tile and goal figures are represented as $n$-point polygons where the similarity between them is measured based on the difference in the positions between the corresponding points. This paper presents alternative similarity measures (distance functions) suitable for this problem. The proposed distance functions focus on the similarity of local structures in several different manners. The designed distance functions are incorporated into a recently developed framework of the exhaustive search of the templates for the Escherization problem. Efficient exhaustive and incomplete search algorithms for the formulated problems are also developed to obtain results within a reasonable computation time. Experimental results showed that the proposed algorithms found satisfactory tile shapes for fairly complicated goal figures in a reasonable computation time., Comment: This is a manuscript currently submitted to a journal

Published
2020

4. An Efficient Algorithm for the Escherization Problem in the Polygon Representation

Author

Nagata, Yuichi and Imahori, Shinji

Subjects
Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms
Abstract

In the Escherization problem, given a closed figure in a plane, the objective is to find a closed figure that is as close as possible to the input figure and tiles the plane. Koizumi and Sugihara's formulation reduces this problem to an eigenvalue problem in which the tile and input figures are represented as $n$-point polygons. In their formulation, the same number of points are assigned to every tiling edge, which forms a tiling template, to parameterize the tile shape. By considering all possible configurations for the assignment of the $n$ points to the tiling edges, we can achieve much flexibility in terms of the possible tile shapes and the quality of the optimal tile shape improves drastically, at the cost of enormous computational effort. In this paper, we propose an efficient algorithm to find the optimal tile shape for this extended formulation of the Escherization problem., Comment: This version has been submitted to an international journal

Published
2019
Full Text
View/download PDF

7. A 2.75-Approximation Algorithm for the Unconstrained Traveling Tournament Problem

Author

Imahori, Shinji, Matsui, Tomomi, and Miyashiro, Ryuhei

Subjects
Computer Science - Data Structures and Algorithms
Abstract

A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality., Comment: 12 pages, 1 figure

Published
2011
Full Text
View/download PDF

8. Escher-like Tilings with Weights

Author

Imahori, Shinji, Kawade, Shizuka, Yamakata, Yoko, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Akiyama, Jin, editor, Ito, Hiro, editor, Sakai, Toshinori, editor, and Uno, Yushi, editor

Published
2016
Full Text
View/download PDF

11. Feature Extraction and Summarization of Recipes Using Flow Graph

Author

Yamakata, Yoko, Imahori, Shinji, Sugiyama, Yuichi, Mori, Shinsuke, Tanaka, Katsumi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Jatowt, Adam, editor, Lim, Ee-Peng, editor, Ding, Ying, editor, Miura, Asako, editor, Tezuka, Taro, editor, Dias, Gaël, editor, Tanaka, Katsumi, editor, Flanagin, Andrew, editor, and Dai, Bing Tian, editor

Published
2013
Full Text
View/download PDF

12. Colorful Strips

Author

Aloupis, Greg, Cardinal, Jean, Collette, Sébastien, Imahori, Shinji, Korman, Matias, Langerman, Stefan, Schwartz, Oded, Smorodinsky, Shakhar, Taslakian, Perouz, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and López-Ortiz, Alejandro, editor

Published
2010
Full Text
View/download PDF

13. An Improved Approximation Algorithm for the Traveling Tournament Problem

Author

Yamaguchi, Daisuke, Imahori, Shinji, Miyashiro, Ryuhei, Matsui, Tomomi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dong, Yingfei, editor, Du, Ding-Zhu, editor, and Ibarra, Oscar, editor

Published
2009
Full Text
View/download PDF

14. Algorithmic Folding Complexity

Author

Cardinal, Jean, Demaine, Erik D., Demaine, Martin L., Imahori, Shinji, Langerman, Stefan, Uehara, Ryuhei, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dong, Yingfei, editor, Du, Ding-Zhu, editor, and Ibarra, Oscar, editor

Published
2009
Full Text
View/download PDF

16. Constructive Algorithms for the Constant Distance Traveling Tournament Problem

Author

Fujiwara, Nobutomo, Imahori, Shinji, Matsui, Tomomi, Miyashiro, Ryuhei, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Burke, Edmund K., editor, and Rudová, Hana, editor

Published
2007
Full Text
View/download PDF

26. Colorful Strips

Author

Aloupis, Greg, Cardinal, Jean, Collette, Sébastien, Imahori, Shinji, Korman, Matias, Langerman, Stefan, Schwartz, Oded, Smorodinsky, Shakhar, and Taslakian, Perouz

Published
2011
Full Text
View/download PDF

27. Algorithmic Folding Complexity

Author

Cardinal, Jean, Demaine, Erik D., Demaine, Martin L., Imahori, Shinji, Ito, Tsuyoshi, Kiyomi, Masashi, Langerman, Stefan, Uehara, Ryuhei, and Uno, Takeaki

Published
2011
Full Text
View/download PDF

30. Colorful Strips

Author

Aloupis, Greg, primary, Cardinal, Jean, additional, Collette, Sébastien, additional, Imahori, Shinji, additional, Korman, Matias, additional, Langerman, Stefan, additional, Schwartz, Oded, additional, Smorodinsky, Shakhar, additional, and Taslakian, Perouz, additional

Published
2010
Full Text
View/download PDF

31. Escherization with Large Deformations Based on As-Rigid-As-Possible Shape Modeling.

Author

Nagata, Yuichi and Imahori, Shinji

Subjects
ENERGY function
Abstract

Escher tiling is well known as a tiling that consists of one or a few recognizable figures, such as animals. The Escherization problem involves finding the most similar shape to a given goal figure that can tile the plane. However, it is easy to imagine that there is no similar tile shape for complex goal shapes. This article devises a method for finding a satisfactory tile shape in such a situation. To obtain a satisfactory tile shape, the tile shape is generated by deforming the goal shape to a considerable extent while retaining the characteristics of the original shape. To achieve this, both goal and tile shapes are represented as triangular meshes to consider not only the contours but also the internal similarity of the shapes. To measure the naturalness of the deformation, energy functions based on traditional as-rigid-as-possible shape modeling are incorporated into a recently developed framework of the exhaustive search of the templates for the Escherization problem. The developed algorithms find satisfactory tile shapes with natural deformations for fairly complex goal shapes. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

32. Algorithmic Folding Complexity

Author

Cardinal, Jean, primary, Demaine, Erik D., additional, Demaine, Martin L., additional, Imahori, Shinji, additional, Langerman, Stefan, additional, and Uehara, Ryuhei, additional

Published
2009
Full Text
View/download PDF

42. Optimizing Train Stopping Patterns for Congestion Management

Author

Yamauchi, Tatsuki, Takamatsu, Mizuyo, Imahori, Shinji, Yamauchi, Tatsuki, Takamatsu, Mizuyo, and Imahori, Shinji

Abstract

In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway lines in Tokyo including Keio Line with six types of trains and succeed in relaxing congestion with a small effect on travel time.

Published
2017
Full Text
View/download PDF

43. Optimizing Train Stopping Patterns for Congestion Management

Author

Tatsuki Yamauchi and Mizuyo Takamatsu and Shinji Imahori, Yamauchi, Tatsuki, Takamatsu, Mizuyo, Imahori, Shinji, Tatsuki Yamauchi and Mizuyo Takamatsu and Shinji Imahori, Yamauchi, Tatsuki, Takamatsu, Mizuyo, and Imahori, Shinji

Abstract

In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway lines in Tokyo including Keio Line with six types of trains and succeed in relaxing congestion with a small effect on travel time.

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results