权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Establishment of Discrete Convexity Paradigm

离散凸范式的建立

基本信息

批准号：
15360043
负责人：
MUROTA Kazuo
金额：
$ 6.53万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

The main aim of this research project is to establish a novel paradigm of discrete convexity by exploiting applications of the theory of discrete convex analysis to fundamental problems in economics, system engineering, operations research, optimization, algorithm science, and others. In this research project, we obtained a number of results described below. All of the results are presented at refereed international conference or accepted for publications in international scientific journals.(1)For optimization problems related to discrete convexity (in particular, for the submodular flow problem with M-convex cost function), we developed a number of efficient algorithms using the capacity scaling technique. The obtained algorithm has the best known complexity bound.(2)We pointed out that the concept of multimodular functions, which had been conceived independently of discrete convex analysis, is essentially equivalent to the concept of L-convex functions. On the basis of this observation we derived some properties including discrete separation.(3)We revealed a close relationship between M-convex functions and tree metrics. Specifically, we proved that the Hessian matrix of a quadratic M-convex function is essentially the same as the negative of the tree metric matrix.(4)We established a discrete fixed point theorem for functions defined on integrally convex sets. The theorem finds applications in mathematical economics and game theory.(5)We provided new characterizations of M-convex functions in terms of gross substitution and single improvement property known in mathematical economics.(6)As applications of discrete convex analysis to mathematical economics, we developed a theory for economic equilibrium models with indivisible goods. We also developed an algorithm for computing a competitive equilibrium using the framework of M-convex submodular flow problem.

本研究项目的主要目的是通过将离散凸分析理论应用于经济学、系统工程、运筹学、最优化、算法科学等领域的基本问题，建立一种新的离散凸性范式。在本研究项目中，我们获得了以下描述的一些结果。所有的结果都在国际会议上发表，或在国际科学期刊上发表。（1）对于与离散凸性相关的优化问题（特别是具有M-凸代价函数的次模流问题），我们利用容量缩放技术发展了一些有效的算法。所得到的算法具有最好的已知的复杂度界。(2)We指出独立于离散凸分析而提出的多模函数的概念本质上等价于L-凸函数的概念。在此基础上，我们得到了一些性质，包括离散分离。(3)We揭示了M-凸函数与树度量之间的密切关系。具体地，我们证明了二次M-凸函数的Hessian矩阵与树度量矩阵的负矩阵本质上相同。(4)We建立了定义在整凸集上的函数的离散不动点定理。该定理在数理经济学和博弈论中有应用。(5)We利用数理经济学中已知的粗替换和单改进性质给出了M-凸函数的新刻画。(6)As摘要将离散凸分析应用于数理经济学，建立了商品不可分的经济均衡模型理论。我们还开发了一个算法计算的竞争平衡使用的M-凸子模块流问题的框架。