课题基金 / 基金详情

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

项目摘要

项目成果

FUJISHIGE Satoru的其他基金

相似基金

相关文献

中文摘要
翻译
我们通过特别关注子模块结构来研究大规模离散优化问题,这是设计高效算法的有效方法。具体来说,我们研究了与网络流、匹配、多流、设施位置、资源分配、图连接、通信网络设计和排队网络相关的离散优化问题,双贪婪算法(如双贪婪多面体和分区)中出现的离散结构,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
DOI: --
发表时间: 2008
期刊:
影响因子: --
作者: [Yoshio Aoki, Goichi Ben, Hyoung Soo Kim, Akihisa Tabata, 平井広志]
通讯作者: 平井広志
DOI: --
发表时间: 2009
期刊:
影响因子: --
作者: [S. Fujishige;S. Isotani]
通讯作者: S. Fujishige;S. Isotani
共 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
    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
    • 依托单位:
    海外基金