Current Research

Study on Approximation Algorithms

The design and analysis of algorithms is a fundamental research endeavor supporting information engineering and information science. Today's Information processing handles a variety of objects such as voice, images, symbols and knowledge. Furthermore, models of computation range from sequential processing by a single computer to parallel processing by multiple computers and even to distributed processing by computers connected through networks. Our research area includes both theoretically and practice-oriented research of algorithms in response to such new waves of information technology. The following list describes our specific research themes.
Design of approximation algorithms
Most discrete problems such as graph problems and combinatorial problems are known to be NP-complete (NP-hard in the case of optimization problems). They are considered intractable since their computation time becomes enormous if we use ordinary computers. In practical applications, however, there are many problems that we must manage to solve even if they are NP-complete (NP-hard). For example, in the area of Operations Research, we have to solve scheduling problems and resource assignment problems for large-scale networks. In Artificial Intelligence, there are many processes that require high-level computation like inferences made in the brain. Accordingly, the design of high-performance approximation algorithms has become an important research area.
Hardness of approximation
For a combinatorial optimization problem that is NP-hard, an approximation algorithm is applied. This is an algorithm that always guaranties a certain ratio of the size of the output to that of the optimal solution. The guaranteed ratio is called the approximation ratio or approximation guarantee of the algorithm. In our study of approximation hardness, we show the limits of such a ratio.
For a graph property p, the edge-contraction problem with respect to p is defined as the problem of finding a set of edges of minimum cardinality whose contraction results in the formation of a graph satisfying the property p. This problem is known to be NP-hard. Our study gives a good lower bound of the approximation ratio for this problem.
Design of hardware algorithm
Distance transform is an important process in image processing. Its application involves morphological filters and computer vision. In this study, we proposed an efficient algorithm for the Euclidean distance transform and its implementation on VLSI. Furthermore, we extended it to an algorithm for 3-D Voronoi tessellation.
Efficient cryptographic computation
In this study, we proposed an efficient method for scalar multiplications used in an elliptic crypto-system.