A Class of Constrained Inverse Bottleneck Optimization Problems under Weighted Hamming Distance

A bottleneck optimization problem is to find a feasible solution that minimizes the maximum weight of edges. In this paper, we consider a class of constrained inverse bottleneck optimization problems under weighted Hamming Distance (HD). Given a feasible solution F*, we aim to modify the weights of edges with a minimum cost under weighted bottleneck such that F* becomes an optimal bottleneck solution to the modified problem and the weighted sum-HD is upper-bounded by a given value. We present a general algorithm to solve the problem and show that it can be reduced to O(|E| log |E|) minimum cut problems.