Graduate School of Science and Engineering Science of Environment and Mathematical Modeling

Discrete Mathematics Laboratory

Staff

MIKI Hiroshi
[Associate Professor]

Acceptable course
Master's degree course
Doctoral degree course

Telephone : +81-774-65-6298
hmiki@mail.doshisha.ac.jp
Office : YE-218
Database of Researchers

Research Topics

1. Min-Plus (Tropical ) Linear Algebra and Combinatorial Optimization Problems from the view point of Tropical Geometry
2. Mathematical Aspects of Various Kinds of Network Optimization Problems on Graphs
3. Polynomial Representation of Cellular Automata and its Application to Stability Analysis

Research Contents

Min-Plus algebra is the algebra (semi-ring) with two kinds of operations “Min” and “Plus”. It has the origin in the shortest path problem on graphs and often arises in the description of the algorithms of network optimization problems. Then, we have to analyze the Min-Plus linear equations in order to get the algorithm for solving combinatorial optimization problems. However, it is not easy because the “Min” operation does not have the inverse. Tropical Geometry is the algebraic geometry on Min-Plus (Tropical) Algebra and treat with piecewise linear figures. In Tropical Geometry, tropical variety as the solution of tropical equations is defined in a wide sense and such extended solutions may give innovative viewpoints in the analysis of tropical equations arising in various kinds of combinatorial optimization problems. So, we investigate algorithms for combinatorial optimization problems, especially for network optimization problems, from the viewpoint of tropical geometry. We express the local transition functions of cellular automata by polynomial functions; by using such expression we can classify Cellular Automata under some group action, specify the class of cellular automata admitting the various kinds of conservation laws. We are going to analyze the stability of some kind of cellular automata appearing in the analysis of traffic model such as SlS model. Such investigation serves to clarify the validity of using cellular automata in the elucidation of traffic jam.

Keywords