KMS Of Academy of mathematics and systems sciences, CAS
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 | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/13281 |
Collection | 中国科学院数学与系统科学研究院 |
Corresponding Author | Cai, MC |
Affiliation | Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China |
Recommended Citation 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. |
Files in This Item: | ||||||
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment