×

Constrained and bicriteria inverse bottleneck optimization problems under weighted Hamming distance. (English) Zbl 1236.49063

Summary: A Bottleneck Optimization Problem (BOP) is to find a feasible solution that minimizes the maximum weight \(w\) of edges. While in an inverse BOP, a candidate solution \(F^*\) is first given, and the aim is to modify weights \(w\) to \(w^*\) under some measure such that \(F^*\) becomes an optimal bottleneck solution with respect to \(w\)*. The Constrained Inverse BOP (CIBOP) is first discussed under weighted bottleneck Hamming Distance (HD), where an upper-bound constraint on the sum-HD between \(w\) and \(w^*\) is added. It is shown that CIBOP can be reduced to \(O(m \log m)\) minimum cut problems, where \(m = |E|\). A class of lexicographic Bicriteria Inverse BOP (BIBOP) are also studied, in which the first objective function can be measured by weighted bottleneck-HD (BIBOP\(_{ bH })\) and weighted \(l _{\infty }\) norm (BIBOP\(_{\infty })\), and the second objective function can be measured by (weighted) sum-HD and weighted \(l _{1}\) norm, respectively. It is shown that BIBOP\(_{ bH }\) and BIBOP\(_{\infty }\) can be solved in time \(O((m + T _{ cf }) \log m + T _{ c })\) and \(O(m ^{2}(\log m + T _{ bc }) + T _{ c })\), respectively, where \(T _{ cf }\) is the time of checking feasibility of a cut, \(T _{ c }\) and \(T _{ bc }\) are the time to find a minimum cut and a minimum bottleneck cut, respectively.

MSC:

49K35 Optimality conditions for minimax problems
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C47 Minimax problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1023/A:1008360312607 · Zbl 0978.90065 · doi:10.1023/A:1008360312607
[2] Dasgupta S, Algorithms (2006)
[3] DOI: 10.1016/j.ejor.2004.07.059 · Zbl 1091.90065 · doi:10.1016/j.ejor.2004.07.059
[4] DOI: 10.1007/11775096_21 · Zbl 1137.90691 · doi:10.1007/11775096_21
[5] DOI: 10.1016/j.cor.2005.12.003 · Zbl 1123.90060 · doi:10.1016/j.cor.2005.12.003
[6] Güler Ç, On inverse network problems and their generalizations, Ph.D. diss. (2009)
[7] DOI: 10.1007/s10878-008-9159-8 · Zbl 1185.90025 · doi:10.1007/s10878-008-9159-8
[8] DOI: 10.1007/s10878-005-5486-1 · Zbl 1066.90104 · doi:10.1007/s10878-005-5486-1
[9] DOI: 10.1023/B:JOCO.0000038914.26975.9b · Zbl 1084.90035 · doi:10.1023/B:JOCO.0000038914.26975.9b
[10] DOI: 10.1007/s10898-008-9294-x · Zbl 1180.90351 · doi:10.1007/s10898-008-9294-x
[11] DOI: 10.1016/j.tcs.2007.12.006 · Zbl 1145.68038 · doi:10.1016/j.tcs.2007.12.006
[12] Schrijver A, Combinatorial Optimization, Polyhedra and Efficiency (2003)
[13] DOI: 10.1145/263867.263872 · Zbl 0891.68071 · doi:10.1145/263867.263872
[14] DOI: 10.1007/BF01539860 · Zbl 0904.90168 · doi:10.1007/BF01539860
[15] DOI: 10.1007/s10878-006-9016-6 · Zbl 1198.90382 · doi:10.1007/s10878-006-9016-6
[16] DOI: 10.1007/s10898-005-6470-0 · Zbl 1098.90062 · doi:10.1007/s10898-005-6470-0
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.