Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-06T08:06:06.705Z Has data issue: false hasContentIssue false
  • English
  • Français

The inverse fractional matching problem

Published online by Cambridge University Press:  17 February 2009

Jianzhong Zhang ,
Zhenhong Liu  and
Zhongfan Ma
Jianzhong Zhang
Affiliation:
Department of Mathematics, City University of Hong Kong, Hong Kong.
Zhenhong Liu
Affiliation:
institute of Systems Sciences, Academia Sinica, Beijing, China.
Zhongfan Ma
Affiliation:
institute of Systems Sciences, Academia Sinica, Beijing, China.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper presents a method for the inverse fractional matching problem. We show that the dual of this inverse problem can be transformed into the circulation flow problem on a directed bipartite graph which can be solved easily. We also give an algorithm to obtain the primal optimum solution of the inverse problem from its dual optimum solution by solving a shortest path problem. Furthermore, we generalize this method to solve the inverse symmetric transportation problem.

Type
Research Article
Information
The ANZIAM Journal , Volume 40 , Issue 4 , April 1999 , pp. 484 - 496
Copyright
Copyright © Australian Mathematical Society 1999

References

[1]Ahuja, R. K., Magnanti, T. L. and Orlin, J. B., Network Flows (Prentice Hall, 1993).Google Scholar
[2]Cai, M. and Li, Y., “Inverse matroid intersection problem”, ZOR Mathematical Methods of Operations Research 45 (1997) 235–243.Google Scholar
[3]Burton, D. and Toint, Ph. L., “On an instance of the inverse shortest paths problem”, Mathematical Programming 53 (1992) 45–61.CrossRefGoogle Scholar
[4]Fekete, S. P. et al. , “The complexity of an inverse shortest paths problem, working report”, Technical report, Center for Parallel Computing, Universität zu Köln, Germany, 1996.Google Scholar
[5]Gondran, M., Minoux, M. and Vajda, S., Graphs and Algorithms (John Wiley & Sons, 1984).Google Scholar
[6]Ma, Z., Xu, S. and Zhang, J., “An algorithm for inverse minimum spanning tree problem”, Optimization Methods and Software, to appear.Google Scholar
[7]Sokkalingam, P. T. et al. , “Inverse spanning tree problem: formulations and algorithm”, Working report 3890–96, Sloan School of Management, MIT, USA, 1996.Google Scholar
[8]Xu, S. and Zhang, J., “An inverse problem of the weighted shortest path problem”, Japan J. Industr. Appl. Math. 12 (1995) 47–59.CrossRefGoogle Scholar
[9]Yang, C. and Zhang, J., “Inverse maximum flow and minimum cut problems”, Optimization 40 (1997) 147–170.CrossRefGoogle Scholar
[10]Zhang, J. and Liu, Z., “Calculating some inverse linear programming problem”, J. Comput. Appl. Math. 72 (1996) 261–273.CrossRefGoogle Scholar
[11]Zhang, J., Liu, Z. and Ma, Z., “On inverse problem of minimum spanning tree with partition constraints”, ZOR Mathematical Methods of Operations Research 44 (1996) 347–358.Google Scholar
[12]Zhang, J. and Ma, Z., “A network flow method for solving some inverse combinatorial optimization problems”, Optimization 37 (1996) 59–72.CrossRefGoogle Scholar
[13]Zhang, J., Ma, Z. and Yang, C., “A column generation method for inverse shortest path problem”, ZOR Mathematical Methods of Operations Research 41 (1995) 347–358.CrossRefGoogle Scholar