Research on Algorithms in Discrete Convex Analysis

本研究项目在离散凸分析算法方面有三个目标：（1）发展M_2凸函数极小化问题的多项式时间算法;（2）研究连续M-/L-凸函数极小化问题的算法;（3）研究离散凸分析与凸函数极小化问题之间的关系。Murota和岩田、Moriguchi等人提出了一个求解M-凸次模流问题的多项式时间算法，它等价于M_2凸函数极小化问题，我们正在研究第二个目标，在第三个目标上，我们得到了一些结果和未来的工作。本文分为两个主题，第一个主题是离散凸分析在双边匹配市场模型中的应用。Fujishige和Tamura利用离散凸分析提出了几种双边匹配模型。这些模型包含许多已知的模型作为特例。他们通过改进M_2-凸函数极小化的算法证明了他们的模型总是有两两稳定的结果。此外，证明了多项式时间算法的情况下，有效域包含在0-1超立方体寻找成对稳定的结果。Tamura和Farooq从数理经济学的角度研究了M-凸函数的性质。第二个课题是跳跃系统中的M-凸函数。Murota给出了跳变系统中M-凸函数的概念、最优性准则和极小化算法，Tamura利用坐标尺度技术提出了一个极小化M-凸函数的多项式时间算法，这是组合优化中的一个新思想。

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.