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

离散凸函数约束优化的高效准确逼近算法的开发

• 批准号: 21740060
• 负责人: SHIOURA Akiyoshi
• 金额: $ 2.83万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21740060/
• 关键词: 離散最適化; 組合せ最適化; 数理計画; 離散凸関数; 近似アルゴリズム; アルゴリズム; マトロイド; 劣モジュラ関数; マトロスド

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.

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

项目成果

Computing the convex closure of discrete convex functions

计算离散凸函数的凸闭包

• 发表时间: 2012
• 作者: 小田川健一;豊田貴嗣;笹川圭右;小林公一;坂本信;田邊裕治;谷藤理;佐藤卓;古賀良生;大森豪;Hideo Koguchi and Naoki Nishi;Akiyoshi Shioura
• 通讯作者: Akiyoshi Shioura

Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra

邻域系统、跳跃系统和双子模多面体

• 发表时间: 2010
• 作者: K. Kobayashi;Y. Toku and M. Muraoka;塩浦昭義
• 通讯作者: 塩浦昭義

A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions

一种计算平衡条件下近乎公平的边缘着色的快速算法

• 发表时间: 2010
• 期刊: Journal of Graph Algorithms and Applications
• 作者: A. Shioura;M. Yagiura
• 通讯作者: M. Yagiura

M-convex function minimization by continuous relaxation approach : proximity theorem and algorithm

通过连续松弛方法最小化 M 凸函数：邻近定理和算法

• 发表时间: 2011
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: S.Moriguchi;A.Shioura;N.Tsuchimura
• 通讯作者: N.Tsuchimura

A Divide-and-Conquer Approach for Polymatroid Optimization with Application to Preemptive Scheduling Problems

多拟阵优化的分治法及其在抢占式调度问题中的应用

• 发表时间: 2009
• 作者: N.Shakhlevich;A.Shioura;V.Strusevich
• 通讯作者: V.Strusevich