CSpace
 Inverse matroid intersection problem Cai, MC; Li, YJ 1997 Source Publication MATHEMATICAL METHODS OF OPERATIONS RESEARCH ISSN 1432-2994 Volume 45Issue:2Pages:235-243 Abstract 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. Keyword inverse matroid intersection problem minimum cost circulation strongly polynomial algorithm Language 英语 WOS Research Area Operations Research & Management Science ; Mathematics WOS Subject Operations Research & Management Science ; Mathematics, Applied WOS ID WOS:000071262600005 Publisher PHYSICA VERLAG GMBH Citation statistics Cited Times:10[WOS]   [WOS Record]     [Related Records in WOS] Document Type 期刊论文 Identifier http://ir.amss.ac.cn/handle/2S8OKBNM/13281 Collection 中国科学院数学与系统科学研究院 Affiliation Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China Recommended CitationGB/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.
 Files in This Item: There are no files associated with this item.
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Google Scholar Similar articles in Google Scholar [Cai, MC]'s Articles [Li, YJ]'s Articles Baidu academic Similar articles in Baidu academic [Cai, MC]'s Articles [Li, YJ]'s Articles Bing Scholar Similar articles in Bing Scholar [Cai, MC]'s Articles [Li, YJ]'s Articles Terms of Use No data! Social Bookmark/Share