Development of Efficient and Accurate Approximation Algorithms for Constrained Optimization of Discrete Convex Functions

本研究的目的是利用离散凸分析的理论，开发在计算时间和解的质量上都有理论保证的算法。在三年的研究期间，我获得了各种新的成果。特别地，我开发了一个多项式时间逼近方案，用于在多个背包约束下最大化m -凹函数。此外，我还揭示了称为邻居系统的一般解集的结构，并证明了在邻居系统上可分离凸函数的最小化可以在多项式时间内解决。

The aim of this research is to develop algorithms with theoretical guarantee for both of computational time and quality of solutions by using the theory of discrete convex analysis. During the three years of the research period, I have obtained various new results. In particular, I developed a polynomial-time approximation scheme for the maximization of an M-concave function under multiple knapsack constraints. In addition, I revealed the structure of a general solution set called a neighbor system, and showed that the minimization of a separable-convex function over a neighbor system can be solved in polynomial time.