×

Inverse bottleneck optimization problems on networks. (English) Zbl 1137.90691

Cheng, Siu-Wing (ed.) et al., Algorithmic aspects in information and management. Second international conference, AAIM 2006, Hong Kong, China, June 20–22, 2006. Proceedings. Berlin: Springer (ISBN 3-540-35157-4/pbk). Lecture Notes in Computer Science 4041, 220-230 (2006).
Summary: The bottleneck optimization problem is to find a feasible solution that minimizes the bottleneck cost. In this paper, we consider the inverse bottleneck optimization problems with bound constraints on modification under weighted \(l_{1}\) norm, weighted sum-Hamming distance and weighted bottleneck-Hamming distance. That is, given a feasible solution \(F^{*}\), we aim to modify the cost function under some measure such that \(F^{*}\) becomes an optimal solution to the bottleneck optimization problem. We show that the inverse problem under weighted \(l_{1}\) norm and weighted sum-Hamming distance can be reduced to \(O(m)\) minimum cut problems, while the inverse problem under weighted bottleneck-Hamming distance can be reduced to \(O(\log m)\) cut feasibility problems, where \(m = |E|\).
For the entire collection see [Zbl 1108.90002].

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI