Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
批准号:
20310088
负责人:
FUJISHIGE Satoru
金额:
$12.56万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (B)
财政年份:
2008
资助国家:
日本
项目状态:
已结题
起止时间:
2008 至 2012
中文摘要
我们通过特别关注子模块结构来研究大规模离散优化问题,这是设计高效算法的有效方法。具体来说,我们研究了与网络流、匹配、多流、设施位置、资源分配、图连接、通信网络设计和排队网络相关的离散优化问题,双贪婪算法(如双贪婪多面体和分区)中出现的离散结构,Horn函数的离散结构和稳定匹配问题,以此来建立基础理论和快速算法通过整合在单个离散结构上获得的知识和见解。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
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
K_3+K_3に対するメトリツク詰込み問題
K_3+K_3 的度量填充问题
DOI:
--
发表时间:
2008
期刊:
影响因子:
--
作者:
[Yoshio Aoki, Goichi Ben, Hyoung Soo Kim, Akihisa Tabata, 平井広志]
通讯作者:
平井広志
DOI:
--
发表时间:
2009
期刊:
影响因子:
--
作者:
[S. Fujishige;S. Isotani]
通讯作者:
S. Fujishige;S. Isotani
Computational geometric approach to submodular function minimization for multiclass queueing systems
多类排队系统子模函数最小化的计算几何方法
DOI:
10.1007/s13160-012-0074-0
发表时间:
2012
期刊:
Japan Journal of Industrial and Applied Mathematics
影响因子:
0.9
作者:
[田村元秀、西川淳、オリビエギヨン、小久保英一郎、芝井広、深川美里、村上浩、中川貴雄、片坐宏一、塩谷圭吾、馬場直志、村上尚史, 他, T. Itoko and S. Iwata]
通讯作者:
T. Itoko and S. Iwata
共 58 条
Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures
-
批准号:16310111
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$10.44万
-
财政年份:2004
-
负责人:FUJISHIGE Satoru
-
依托单位:
Fundamental Research on Fast Algorithms for Large-Scale Discrete Optimization Problems Based on Submodularity Structures
-
批准号:13480113
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$4.61万
-
财政年份:2001
-
负责人:FUJISHIGE Satoru
-
依托单位:
Basic Studies on Submodular Structure of Large-scale Combinatorial Systems
-
批准号:10680429
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.11万
-
财政年份:1998
-
负责人:FUJISHIGE Satoru
-
依托单位:
Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
-
批准号:10205217
-
项目类别:Grant-in-Aid for Scientific Research on Priority Areas (B)
-
资助金额:$11.2万
-
财政年份:1998
-
负责人:FUJISHIGE Satoru
-
依托单位:
Fundamental Studies on Large-Scale combinatorial Systems Based on Submodular Analysis
-
批准号:04832006
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.28万
-
财政年份:1992
-
负责人:FUJISHIGE Satoru
-
依托单位:
Analysis of Combinatorial Optimization Problems with Submodular Structures and Design of Efficient Algorithms
-
批准号:01540168
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$0.64万
-
财政年份:1989
-
负责人:FUJISHIGE Satoru
-
依托单位:
海外基金