Solution Structure of Some Inverse Combinatorial Optimization Problems

Jianzhong Zhang and Zhongfan Ma
Additional contact information
Jianzhong Zhang: City University of Hong Kong
Zhongfan Ma: Academia Sinica

Journal of Combinatorial Optimization, 1999, vol. 3, issue 1, No 10, 127-139

Abstract: Abstract In this paper we consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions of an optimization problem, we wish to know: under what weight vectors (or capacity vectors) will these feasible solutions become optimal solutions? We analysed shortest path problem, minimum cut problem, minimum spanning tree problem and maximum-weight matching problem, and found that in each of these cases, the solution set of the inverse problem is charaterized by solving another combinatorial optimization problem. The main tool in our approach is Fulkerson's theory of blocking and anti-blocking polyhedra with some necessary revisions.

Keywords: inverse problem; shortest path; minimum spanning tree; maximum-weight matching; blocking and anti-blocking polyhedra (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009829525096 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:1:d:10.1023_a:1009829525096

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

DOI: 10.1023/A:1009829525096

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 ().