×

Inverse min-max spanning tree problem under the weighted sum-type Hamming distance. (English) Zbl 1145.68038

Summary: The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present a combinatorial algorithm that runs in strongly polynomial times.

MSC:

68R10 Graph theory (including graph drawing) in computer science
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Camerini, P. M., The min-max spanning tree problem and some extensions, Information Processing Letters, 7, 10-14 (1978) · Zbl 0373.05028
[2] Yang, X. G.; Zhang, J. Z., Some inverse min-max network problems under weighted \(l_1\) and \(l_\infty\) norms with bound constraints on changes, Journal of Combinatorial Optimization, 13, 123-135 (2007) · Zbl 1198.90382
[3] Heuberger, C., Inverse optimization: A survey on problems, methods, and results, Journal of Combinatorial Optimization, 8, 329-361 (2004) · Zbl 1084.90035
[4] He, Y.; Zhang, B. W.; Yao, E. Y., Weighted inverse minimum spanning tree problems under Hamming distance, Journal of Combinatorial Optimization, 9, 91-100 (2005) · Zbl 1066.90104
[5] He, Y.; Zhang, B. W.; Zhang, J. Z., Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance, Journal of Global Optimization, 34, 3, 47-474 (2006) · Zbl 1098.90062
[6] Zhang, B. W.; Zhang, J. Z.; He, Y., The center location improvement problem under the Hamming distance, Journal of Combinatorial Optimization, 9, 187-198 (2005) · Zbl 1079.90084
[7] Yang, X. G.; Zhang, J. Z., (Some New Results on Inverse Sorting Problems. Some New Results on Inverse Sorting Problems, Lecture Notes in Computer Science, vol. 3595 (2005)), 985-992 · Zbl 1128.68351
[8] Liu, L. C.; Zhang, J. Z., Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12, 395-408 (2006) · Zbl 1126.90070
[9] Liu, L. C.; Yao, E. Y., Weighted inverse minimum cut problem under the bottleneck type Hamming distance, Asia-Pacific Journal of Operational Research, 24, 5, 725-736 (2007) · Zbl 1159.90319
[10] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 1201.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.