Combinatorial Optimization, Algorithms, and Operations Research

When you want to go from a point A to another point B as fast as possible, a navigation system such as Google Map quickly tells us which route is the best. Behind this, in addition to how accurate the map data is and how fast the computers can perform procedures, the power of algorithms, concrete procedures of computation, plays an important role. To obtain the same result from the same input, the computational time or space of algorithms may be significantly different; for example, it is possible that one finishes within 0.1 second but another does not finish within a year. Thus, it is very important to design and select an efficient algorithm when you want to solve a problem.

I mainly study combinatorial optimization, where we want to find the "best" combination in a given criterion subject to a given constraint, such as the aforementioned routing problem. As well as considering efficient algorithms for (or sometimes hardness of) individual problems, I am interested in "what kind of combinatorial structures or properties make the problems easy or difficult", and investigate such a question related to discrete mathematics (graphs, matroids, submodularity, discrete convexity, etc.).

In the real world, there are many types of requirements, e.g., we want to assign students to laboratories (research groups) in a fair manner, we want to invest money with low risk and high return, and we want to design networks (for electricity distribution, transportation, or telecommunication) with low cost and high reliability. Operations research is a mathematical study for supporting decision making in such situations by formulating realistic (or sometimes unrealistic) situations as mathematical models and analyzing them. Our research group including I studies a variety of topics in operations research, which are not restricted to combinatorial optimization and discrete algorithms.