On Algorithms and Applications of Semidefinite Programming to Combinatorial Optimization

我们在半定规划和离散凸分析方面取得了若干成果，并在算法与计算国际学术会议、整数规划与组合优化国际学术会议等国际会议上发表。在这里，我们解释其中的七个结果。Fujie和Tamura将最大权稳定集问题的凸集松弛理论推广到广义稳定集问题。他们还对最大权稳定集问题的几个结果给出了简单的证明。2) Murota等证明了群对称半定规划的数值解是群对称的。3) Murota等人给出了在大规模和稀疏半确定程序的所有数据矩阵上利用聚合稀疏性模式的框架。4) Murota和Tamura利用m -凸子模流问题给出了一种判定经济模型中是否存在竞争均衡的有效算法。Tamura设计了一种新的标度技术和m -凸函数最小化问题的高效算法。6) Murota和Tamura证明了若干离散凸函数的邻近定理，如m2 -凸函数、l2 -凸函数等。7) Tamura给出了一个技术性的结果，即任何l2 -凸函数都可以用两个l -凸函数的卷积来表示，在卷积的定义中得到了极小值。这个结果为l2 -凸函数的几个已知结果提供了简单的证明。

We obtained several results on semidefinite programming and discrete convex analysis and presented these results at international conferences, e.g., International Symposium on Algorithms and Computation, Conference on Integer Programming and Combinatorial Optimization and so on. Here we explain seven results among these.1) Fujie and Tamura generalized the theory of a convex set relaxation for the maximum weight stable set problem to the generalized stable set problem. They also gave simple proofs for several results for the maximum weight stable set problem.2) Murota et al. proved that the numerically obtained solution of group symmetric semidefinite program is group symmetric.3) Murota et al. gave a framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs.4) Murota and Tamura gave an efficient algorithm to decide whether a competitive equilibrium exists or not in some economic model by utilizing M-convex submodular flow problem.5) Tamura devised a new scaling technique and an efficient algorithm for M-convex function minimization problem.6) Murota and Tamura proved proximity theorems for several discrete convex functions, for example, M2-convex functions, L2-convex functions and so on.7) Tamura showed a technical result that any L2-convex function can be represented by the convolution of two L-convex functions attaining the infimum in the definition of the convolution. This result gives simple proofs for several known results on L2-convex functions.