期刊文献+

简单网络流对策的相对N-核

Relative Nucleolus of Flow Game on Simple Network
原文传递
导出
摘要 主要研究简单网络流对策中相对N-核的算法.当网络中最大流值等于1时,证明相对N-核与对策的核心相同,不一定是单点集;而当网络中最大流值大于1时,利用Kopelowitz's序列线性规划方法和线性规划对偶理论,证明相对N-核与N-核相同(同为单点集),并且可在局中人个数的多项式时间内得到求解. This paper focuses on the relative nucleolus of the flow game defined on a simple network. When the value of the maximum flow in the network is 1, the relative nucleolus coincides with the core. On the other hand, when the value of the maximum flow in the network is greater than 1, the relative nucleolus coincides with the original nucleolus. The main techniques in our proofs are Kopelowitz's sequential linear programming method and linear programming duality theorem. These results yield that the relative nucleolus of a simple flow game can be computed in polynomial time.
出处 《数学的实践与认识》 CSCD 北大核心 2011年第6期125-132,共8页 Mathematics in Practice and Theory
基金 国家自然科学基金(10771200)
关键词 网络流 线性规划 对偶 核心 N-核 network flow linear programming duality core nucleolus
  • 相关文献

参考文献9

  • 1Schmeidler D. The nucleolus of a characteristic function game[J]. SIAM Journal of Applied Math- ematics, 1969, 17: 116-1170.
  • 2Kopelowitz A. Computation of the kernels of simple games and the nucleolus of n-person games [A]. RM-31[C]. Math. Dept:The ttebre University of Jerusalem, 1967.
  • 3Kalai E. Zemel E. Generalized network problems yielding totally balanced games[J]. Operations Research, 1982, 30: 998-1008.
  • 4Deng X, Ibaraki T. Nagamochi H. Algorithmic aspects of the core of combinatorial optimization games[J]. Mathematics of Operations Research, 1999, 24(2): 751-766.
  • 5Deng X ,Fang Q , Sun X. Finding nucleolus of flow game[A]. Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm[C]. SODA 2006, 2006, 124-131.
  • 6Kern W, Paulusma D. Matching games: the least core and the nucleolus[J]. Mathematics of Oper- ations Research, 2003,28 : 294-308.
  • 7Faigle U, Kern W, Kuipers J. Computing the nucleolus of min-cost spanning Tree games is NP- hard[J]. International Journal of Game. Theory, 1998, 27: 443-450.
  • 8Faigle U, Kern W. Fekete S P W. Hochstattler. The nucleon of cooperative games and an algorithm for matching games[J]. Mathematical Programming, 1998, 83: 195-211.
  • 9Huberman G. The nucleolus and the essential coalitions[A]. Analysis and Optimizations of Sys- tems[C]. Berlin: Springer, 1980, 416-422.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部