A General Model of Some Inverse Combinatorial Optimization Problems and Its Solution Method Under l ∞ Norm

Jianzhong Zhang and Zhenhong Liu
Additional contact information
Jianzhong Zhang: City University of Hong Kong
Zhenhong Liu: Academia Sinica

Journal of Combinatorial Optimization, 2002, vol. 6, issue 2, No 7, 207-227

Abstract: Abstract This paper proposes an optimization model and shows that most inverse combinatorial optimization problems so far discussed can be fit into this model as special cases. We propose a Newton-type algorithm for this model under l ∞ norm. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time for any fixed value of the parameter appearing in the subproblem, and it is shown that most particular inverse optimization problems encountered are this kind. Therefore, through this paper we show that a large group of inverse optimization problems can be handled in a uniform way and solved in strongly polynomial time.

Keywords: path; cycle; mean-cycle; assignment; spanning tree; matching; matroid intersection; basis (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1023/A:1013807829021 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:6:y:2002:i:2:d:10.1023_a:1013807829021

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

DOI: 10.1023/A:1013807829021

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