CSpace
 Inverse problems of matroid intersection Cai, MC 1999-12-01 Source Publication JOURNAL OF COMBINATORIAL OPTIMIZATION ISSN 1382-6905 Volume 3Issue:4Pages:465-474 Abstract In this paper we study the inverse problem of matroid intersection: Two matroids M-1 = (E, I-1) and M-2 = (E, I-2), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections. Keyword Inverse problem matroid intersection minimum cost circulation strongly polynomial algorithm Language 英语 WOS Research Area Computer Science ; Mathematics WOS Subject Computer Science, Interdisciplinary Applications ; Mathematics, Applied WOS ID WOS:000084252700008 Publisher KLUWER ACADEMIC PUBL Citation statistics Document Type 期刊论文 Identifier http://ir.amss.ac.cn/handle/2S8OKBNM/14505 Collection 中国科学院数学与系统科学研究院 Corresponding Author Cai, MC Affiliation Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China Recommended CitationGB/T 7714 Cai, MC. Inverse problems of matroid intersection[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,1999,3(4):465-474. APA Cai, MC.(1999).Inverse problems of matroid intersection.JOURNAL OF COMBINATORIAL OPTIMIZATION,3(4),465-474. MLA Cai, MC."Inverse problems of matroid intersection".JOURNAL OF COMBINATORIAL OPTIMIZATION 3.4(1999):465-474.
 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 Baidu academic Similar articles in Baidu academic [Cai, MC]'s Articles Bing Scholar Similar articles in Bing Scholar [Cai, MC]'s Articles Terms of Use No data! Social Bookmark/Share