Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (2): 355-364.doi: 10.1007/s40305-018-0231-5

Special Issue: Discrete optimization

Previous Articles     Next Articles

Inverse Generalized Minimum Cost Flow Problem Under the Hamming Distances

Mobarakeh Karimi1, Massoud Aman1, Ardeshir Dolati2   

  1. 1 Faculty of Mathematics and Statistics, University of Birjand, Birjand, Iran;
    2 Department of Computer Science, Shahed University, Tehran, Iran
  • Received:2017-12-08 Revised:2018-09-10 Online:2019-06-30 Published:2019-06-30
  • Contact: Massoud Aman, Mobarakeh Karimi, Ardeshir Dolati E-mail:mamann@birjand.ac.ir;mobarake.karimi@birjand.ac.ir;dolati@shahed.ac.ir

Abstract: Given a generalized minimum cost flow problem, the corresponding inverse problem is to find a minimal adjustment of the cost function so that the given generalized flow becomes optimal to the problem. In this paper, we consider both types of the weighted Hamming distances for measuring the adjustment. In the sum-type case, it is shown that the inverse problem is APX-hard. In the bottleneck-type case, we present a polynomial time algorithm.

Key words: Generalized minimum cost flow, Inverse problem, Hamming distance, Binary search