Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (3): 399-407.doi: 10.1007/s40305-019-00255-y

所属专题: Discrete optimization

• • 上一篇    下一篇

  

  • 收稿日期:2018-09-11 修回日期:2019-04-06 出版日期:2019-09-30 发布日期:2019-10-08
  • 通讯作者: Da-Chuan Xu, Min Li, Dong-Lei Du, Zhen-Ning Zhang E-mail:xudc@bjut.edu.cn;liminemily@sdnu.edu.cn;ddu@unb.ca;zhangzhenning@bjut.edu.cn
  • 基金资助:
    This research was supported by Higher Educational Science and Technology Program of Shandong Province (No. J17KA171), Natural Science and Engineering Research Council of Canada (No. 06446), the National Natural Science Foundation of China (No. 11871081), and Science and Technology Program of Beijing Education Commission (No. KM201810005006).

A Note on Submodularity Preserved Involving the Rank Functions

Min Li1, Dong-Lei Du2, Da-Chuan Xu3, Zhen-Ning Zhang3   

  1. 1 School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China;
    2 Faculty of Business Administration, University of New Brunswick, Fredericton, Canada;
    3 College of Applied Sciences, Beijing University of Technology, Beijing 100124, China
  • Received:2018-09-11 Revised:2019-04-06 Online:2019-09-30 Published:2019-10-08
  • Contact: Da-Chuan Xu, Min Li, Dong-Lei Du, Zhen-Ning Zhang E-mail:xudc@bjut.edu.cn;liminemily@sdnu.edu.cn;ddu@unb.ca;zhangzhenning@bjut.edu.cn

Abstract: In many kinds of games with economic significance, it is very important to study the submodularity of functions. In this paper, we mainly study the problem of maximizing a concave function over an intersection of two matroids. We obtain that the submodularity may not be preserved, but it involves one maximal submodular problem (or minimal supermodular problem) with some conditions. Moreover, we also present examples showing that these conditions can be satisfied.

Key words: Matroid, Submodular function, Rank function, Convex closure, Game

中图分类号: