Constrained and bicriteria inverse bottleneck optimization problems under weighted Hamming distance

Abstract

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 problem (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(mlog m) minimum cut problems, where m = |E|. A class of lexicographic bicriteria inverse problems (BIBOP) are also studied, in which the first objective function can be measured by weighted bottleneck-HD (BIBOP _bH ) and weighted l _∞ norm (BIBOP_∞), and the second objective function can be measured by (weighted) sum-HD and weighted l ₁ norm, respectively. It is shown that (BIBOP _bH ) and (BIBOP_∞) can be solved in time O((m + T _cf ) log m + T _c ) and O(m ²(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.

Keywords:

• inverse bottleneck optimization problem
• Hamming distance
• bicriteria inverse problem
• minimum cut

AMS Subject Classifications::

• 49K35
• 90B10
• 90C27
• 90C35
• 90C47

Acknowledgements

The authors are grateful to anonymous referees for their helpful comments. This research is supported by NSFC (10626013,10801031), Science Foundation of Southeast University (9207011468) and Excellent Young Teacher Financial Assistance Scheme for teaching and research of Southeast University (4007011028).