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

Exploitation of Applications of Discrete Convex Analysis

离散凸分析应用的开发

基本信息

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

项目摘要

The main aim of this research project is to exploit applications of the theory of discrete convex analysis proposed by the head investigator in the last decade. In this research project, we obtained various results described below. All of the results are presented at refereed international conferences and/ or accepted for publications in international scientific journals.(1) In the area of mathematical economics we obtained three results as applications of discrete convex analysis. First of all, we developed a theory for economic equilibrium models with indivisible goods ; in particular, we investigated sufficient conditions for the existence of competitive equilibrium in an exchange economy with indivisible goods. Secondly, we provide new characterizations of M-convex functions which play a central role in discrete convex analysis. These characterizations are based on well-known concepts in mathematical economics such as the gross substitutes condition and the single improvement condition. Thirdly, we developed an algorithm for computing a competitive equilibrium in an exchange economy with indivisible goods. This algorithm is based on M-convex submodular flow problem which is an optimization problem in discrete convex analysis.(2) We showed a proximity theorem for M-convex function minimization and developed fast algorithms.(3) We discussed combinatorial structure in engineering system from the viewpoint of discrete convex analysis. In particular, we investigated the delta matroid parity problem with the aim of determining the solvability of electrical circuits, and developed an efficient algorithm.(4) We verified applicability of the algorithms in discrete convex analysis to several problems in operations research. Based on this result, we developed efficient algorithms for the network design problem and the max cut problem.

该研究项目的主要目的是利用首席研究员在过去十年中提出的离散凸分析理论的应用。在本研究项目中，我们获得了以下描述的各种结果。所有研究结果都在国际会议上发表，并/或在国际科学期刊上发表。(1)在数理经济学领域中，作为离散凸分析的应用，我们得到了三个结果。首先，我们发展了商品不可分的经济均衡模型的理论;特别地，我们研究了商品不可分的交换经济中竞争均衡存在的充分条件。其次，我们给出了在离散凸分析中起核心作用的M-凸函数的新刻画。这些刻画是基于数理经济学中的著名概念，如总替代条件和单一改进条件。第三，我们开发了一个算法，用于计算一个交换经济中的竞争均衡与不可分割的商品。该算法基于离散凸分析中的一个优化问题M-凸次模流问题。(2)给出了M-凸函数极小化的一个近似定理，并给出了快速算法。(3)从离散凸分析的观点出发，讨论了工程系统的组合结构。特别是，我们研究了delta拟阵奇偶问题，目的是确定电路的可解性，并开发了一种有效的算法。(4)我们验证了离散凸分析算法的适用性，在运筹学中的几个问题。基于这个结果，我们开发了有效的算法，网络设计问题和最大割问题。