Inverse Problems of Matroid Intersection

Cai Mao-Cheng ()
Additional contact information
Cai Mao-Cheng: Academia Sinica

Journal of Combinatorial Optimization, 1999, vol. 3, issue 4, No 8, 465-474

Abstract: Abstract In this paper we study the inverse problem of matroid intersection: Two matroids M 1 = (E, $${\mathcal{I}}$$ 1) and M 2 = (E, $${\mathcal{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.

Keywords: Inverse problem; matroid intersection; minimum cost circulation; strongly polynomial algorithm (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009883605691 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:3:y:1999:i:4:d:10.1023_a:1009883605691

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009883605691

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().