Inverse matroid intersection problem

CSpace

	Inverse matroid intersection problem
	Cai, MC; Li, YJ
	1997
发表期刊	MATHEMATICAL METHODS OF OPERATIONS RESEARCH
ISSN	1432-2994
卷号	45 期号:2 页码:235-243
摘要	Let M-1 and M-2 be matroids on S, B be their k-element common independent set, and w a weight function on S. Given two functions b greater than or equal to 0 and c greater than or equal to 0 on S, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight function w' such that (a) B becomes a maximum weight common independent set of cardinality k under w', (b) c\w' - w\ is minimum, and (c) \w' - w\ less than or equal to b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP. In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets.
关键词	inverse matroid intersection problem minimum cost circulation strongly polynomial algorithm
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000071262600005
出版者	PHYSICA VERLAG GMBH
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/13281
专题	中国科学院数学与系统科学研究院
通讯作者	Cai, MC
作者单位	Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Cai, MC,Li, YJ. Inverse matroid intersection problem[J]. MATHEMATICAL METHODS OF OPERATIONS RESEARCH,1997,45(2):235-243.
APA	Cai, MC,&Li, YJ.(1997).Inverse matroid intersection problem.MATHEMATICAL METHODS OF OPERATIONS RESEARCH,45(2),235-243.
MLA	Cai, MC,et al."Inverse matroid intersection problem".MATHEMATICAL METHODS OF OPERATIONS RESEARCH 45.2(1997):235-243.