- Home
- Programs & Courses
- Graduate School of Science and Engineering : Science of Environment and Mathematical Modeling (Laboratories : Discrete Mathematics Laboratory)

## Graduate School of Science and Engineering

Science of Environment and Mathematical Modeling

### Discrete Mathematics Laboratory

#### Staff

#### Research Topics

<1> Maximum likelihood decoding of two-dimensional codes using a Groebner basis

The Ikegami-Kaji algorithm that performs two-dimensional maximum likelihood decoding using a Groebner basis requires too much computational time to be of practical use. In view of this problem, in this research we consider whether a Groebner basis of the ideal necessary for maximum likelihood decoding can be derived from combinatorial properties of the codes. Such an attempt might lead to the opening of a new vista on the mathematical structure of codes and the mechanism of maximum likelihood decoding.

<2> Groebner basis and the problem of network optimization

In many cases, the problem of network optimization can be formulated as an integer programming problem. Consequently, based upon this problem, a toric ideal can be defined. We investigate the relationship between generators or Groebner bases of such toric ideal and network structures.

<3> Various problems of combinatorial optimization in bioinformatics

In the field of bioinformatics, various combinatorial optimization problems occur that are also of interest from an optimization problem perspective. By formulating such problems as integer programming problems, we study their mathematical structures.

The Ikegami-Kaji algorithm that performs two-dimensional maximum likelihood decoding using a Groebner basis requires too much computational time to be of practical use. In view of this problem, in this research we consider whether a Groebner basis of the ideal necessary for maximum likelihood decoding can be derived from combinatorial properties of the codes. Such an attempt might lead to the opening of a new vista on the mathematical structure of codes and the mechanism of maximum likelihood decoding.

<2> Groebner basis and the problem of network optimization

In many cases, the problem of network optimization can be formulated as an integer programming problem. Consequently, based upon this problem, a toric ideal can be defined. We investigate the relationship between generators or Groebner bases of such toric ideal and network structures.

<3> Various problems of combinatorial optimization in bioinformatics

In the field of bioinformatics, various combinatorial optimization problems occur that are also of interest from an optimization problem perspective. By formulating such problems as integer programming problems, we study their mathematical structures.

#### Research Contents

Optimization refers to the process of either maximizing or minimizing an objective function under a given set of constraints. As such, it represents a typical research topic in applied mathematics. Optimization problems are of two types: a continuous optimization problem in which the treated variable takes continuous values, and a discrete optimization problem in which the variable takes discrete values. Our laboratory is principally devoted to the study of discrete optimization problems, in particular, integer programming problems, in terms of their mathematical structures and from a mathematical point of view. The keyword is either toric ideal or lattice ideal. The tools we use are the Groebner bases of an ideal in the polynomial ring. Specific discrete optimization problems that we are pursuing and that are of considerable interest include the graphical network optimization problem, the problem of maximum likelihood decoding in error correcting codes, and various combinatorial optimization problems in bioinformatics.

#### Keywords

- Optimization problem
- Discrete structure
- Formula manipulation
- Groebner basis

- Toric ideal
- Error correcting code
- Bioinformatics