Some inverse min-max network problems under weighted l 1 and l ∞ norms with bound constraints on changes

Xiaoguang Yang () and Jianzhong Zhang
Additional contact information
Xiaoguang Yang: Chinese Academy of Sciences
Jianzhong Zhang: The Chinese University of Hong Kong

Journal of Combinatorial Optimization, 2007, vol. 13, issue 2, No 2, 123-135

Abstract: Abstract We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l 1 norm or weighted l ∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.

Keywords: Inverse min-max network problem; Weighted l 1 norm; Weighted l∞ norm; Bound constraints; Polynomial time algorithms (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9016-6 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:13:y:2007:i:2:d:10.1007_s10878-006-9016-6

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

DOI: 10.1007/s10878-006-9016-6

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