Shin-Ichi Minato

Shin-Ichi Minato

Auto-generated profile, based on publicly available information

Shin-Ichi Minato

Kyoto University

Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 January 2019 in Japanese Journal of Statistics and Data Science
Verified
Journal Article
Closed access
PDF file
FIFumio Ishioka
Fumio Ishioka
JKJun Kawahara
Jun Kawahara
MMMasahiro Mizuta
Masahiro Mizuta
SMShin-Ichi Minato
Shin-Ichi Minato
KKKoji Kurihara
Koji Kurihara

8 March 2025
Verified
Book Chapter
Open access
PDF file
MBMutsunori Banbara
Mutsunori Banbara
KHKenji Hashimoto
Kenji Hashimoto
THTakashi Horiyama
Takashi Horiyama
KOKosuke Oguri
Kosuke Oguri
SMShin-Ichi Minato
Shin-Ichi Minato
NYNorihito Yasuda
Norihito Yasuda
A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit squares edge to edge. These two notions were first introduced and investigated by Solomon W. Golomb in the 1950s and popularized by Martin Gardner in the 1960s. Since then, dozens of studies have been made in communities of recreational mathematics and puzzles. We first focus on the specific rep-tiles that have been investigated in these communities. Since the notion of rep-tiles is so simple that can be formulated mathematically in a natural way, we can apply a representative puzzle solver, a MIP solver, and SAT-based solvers for solving the rep-tile problem in common. In comparing their performance, we can conclude that the SAT-based solvers are the strongest in the context of simple puzzle solving. We then turn to analyses of the specific rep-tiles. Using some properties of the rep-tile patterns found by solvers, we can complete analyses of specific rep-tiles up to certain sizes, and find new series of solutions for the rep-tiles which have never been found.

6 December 2011
Verified
Conference Paper
Open access
PDF file
TITakeru Inoue
Takeru Inoue
FTFujio Toriumi
Fujio Toriumi
YSYasuyuki Shirai
Yasuyuki Shirai
SMShin-Ichi Minato
Shin-Ichi Minato

17 August 2018 in Algorithms
Verified
Journal Article
Open access
PDF file
SDShuhei Denzumi
Shuhei Denzumi
JKJun Kawahara
Jun Kawahara
KTKoji Tsuda
Koji Tsuda
HAHiroki Arimura
Hiroki Arimura
SMShin-Ichi Minato
Shin-Ichi Minato
KSKunihiko Sadakane
Kunihiko Sadakane
In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been applied to web information retrieval, information integration, and data mining. However, to support rich manipulation of sets of combinations and update ZDDs in the future, ZDDs need too much space, which means that there is still room to be compressed. The paper introduces a new succinct data structure, called DenseZDD, for further compressing a ZDD when we do not need to conduct set operations on the ZDD but want to examine whether a given set is included in the family represented by the ZDD, and count the number of elements in the family. We also propose a hybrid method, which combines DenseZDDs with ordinary ZDDs. By numerical experiments, we show that the sizes of our data structures are three times smaller than those of ordinary ZDDs, and membership operations and random sampling on DenseZDDs are about ten times and three times faster than those on ordinary ZDDs for some datasets, respectively.

20 February 2020
Verified
Book Chapter
Closed access
PDF file
YNYu Nakahata
Yu Nakahata
JKJun Kawahara
Jun Kawahara
THTakashi Horiyama
Takashi Horiyama
SMShin-Ichi Minato
Shin-Ichi Minato

1 September 2018 in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Verified
Journal Article
Closed access
PDF file
HSHirofumi Suzuki
Hirofumi Suzuki
SMShin-Ichi Minato
Shin-Ichi Minato
Finding Pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on the 0-1 multi-objective knapsack problem, and present an algorithm to enumerate all its Pareto-optimal solutions, which improves upon the method proposed by Bazgan et al. Our algorithm is based on dynamic programming techniques using an efficient data structure called zero-suppressed binary decision diagram (ZDD), which handles a set of combinations compactly. In our algorithm, we utilize ZDDs for storing all the feasible solutions compactly, and pruning inessential partial solutions as quickly as possible. As an output of the algorithm, we can obtain a useful ZDD indexing all the Pareto-optimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three- and four-objective instances, which are difficult problems to solve.