Research on Algorithms in Discrete Convex Analysis

点击翻译按钮获取中文摘要

This research project had three aims on algorithms in discrete convex analysis : (1)development of a polynomial time algorithm for minimization of M_2 convex function ; (2)study on algorithms for minimizing continuous M-/L-convex functions ; and (3)study on relations between discrete convex analysis and convex function minimization problems.Our group achieved the first aim. Murota who is one of our group together with Iwata and Moriguchi, developed a polynomial time algorithm for solving M-convex submodular flow problem which is equivalent to M_2 convex function minimization.We are investigating the second aim.On the third aim, we obtained several results and future works. These are divided into two subjects.The first subject is an application of discrete convex analysis to two-sided matching market models. Fujishige and Tamura proposed several two-sided matching models by utilizing discrete convex analysis. These models contain many known models as special cases. They proved that their models always have pairwise-stable outcomes by modifying an algorithm for M_2-convex function minimization. Moreover, the proofs give polynomial time algorithms for finding pairwise-stable outcomes in the case where effective domains are contained in 0-1 hypercubes. Tamura together with Farooq investigated properties of M-convex functions in terms of mathematical economics.The second subject is M-convex functions in jump systems. Murota gave a concept of M-convex functions in jump systems, an optimality criterion of these functions, a minimization algorithm.Moreover, Tamura proposed a polynomial time algorithm for minimizing an M-convex function by using coordinatewise scaling technique which is a new idea in combinatorial optimization.