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

Special Issue: Discrete optimization

Previous Articles     Next Articles

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

CLC Number: