Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures

基于子模结构的离散优化基本理论和快速算法的发展

• 批准号: 20310088
• 负责人: FUJISHIGE Satoru
• 金额: $ 12.56万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20310088/
• 关键词: OR; 離散最適化; アルゴリズム; 劣モジュラ関数; 組合せ最適化; 数理計画; 細合せ最滴化

We have investigated large-scale discrete optimization problems by paying special attention to submodular structures which are effective to devise efficient algorithms. Specifically we have examined discrete optimization problems related to network flows, matchings, multiflows, facility location, resource allocation,graph connectivity, communication network design, and queueing networks, discrete structures arisen in dual greedy algorithms such as dual greedy polyhedra and zonotopes,discrete structures for Horn functions and stable matching problems, and so on to establish the fundamental theory and fast algorithms by integrating the knowledge and insights gained on the individual discrete structures．

我们研究了大规模离散优化问题，特别关注了子模块结构，这是设计高效算法的有效方法。具体地说，我们研究了与网络流、匹配、多流、设施选址、资源分配、图连通性、通信网络设计和排队网络有关的离散优化问题，对偶贪婪算法中出现的离散结构，如对偶贪婪多面体和区域搜索，Horn函数的离散结构和稳定匹配问题等，通过整合在单个离散结构上获得的知识和见解，建立了基础理论和快速算法。

项目成果

Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers

具有多个服务器的封闭 Jackson 网络的随机逼近方案和完美采样器

• DOI: 10.1007/s10479-008-0317-2
• 发表时间: 2008
• 期刊: Annals of Operations Research
• 影响因子: 4.8
• 作者: K.Yasuda;M.Niraula;Y.Agata;S.Kijima and T.Matsui
• 通讯作者: S.Kijima and T.Matsui

K_3+K_3に対するメトリツク詰込み問題

K_3+K_3 的度量填充问题

• 发表时间: 2008
• 作者: Yoshio Aoki;Goichi Ben;Hyoung Soo Kim;Akihisa Tabata;平井広志
• 通讯作者: 平井広志

Polynomial time approximate or perfect samplers for discretized Dirichlet distribution

离散狄利克雷分布的多项式时间近似或完美采样器

• DOI: 10.1007/s13160-010-0002-0
• 发表时间: 2010
• 期刊: Japan Journal of Industrial and Applied Mathematics
• 影响因子: 0.9
• 作者: T. Matsui;M.Motoki;N.Kamatani;and S. Kijima
• 通讯作者: and S. Kijima

On the Boolean connectivity problem for Horn relations

Horn关系的布尔连通性问题

• DOI: 10.1016/j.dam.2010.08.019
• 发表时间: 2010
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: K. Makino;S.Tamaki;and M. Yamamoto
• 通讯作者: and M. Yamamoto

A Submodular Function Minimization Algorithm Based on the Minimum-Norm Base ⁄

• 发表时间: 2009
• 作者: S. Fujishige;S. Isotani