Inverse problems of matroid intersection

CSpace

	Inverse problems of matroid intersection
	Cai, MC
	1999-12-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	3 期号:4 页码:465-474
摘要	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.
关键词	Inverse problem matroid intersection minimum cost circulation strongly polynomial algorithm
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000084252700008
出版者	KLUWER ACADEMIC PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/14505
专题	中国科学院数学与系统科学研究院
通讯作者	Cai, MC
作者单位	Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/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.