赋权哈明距离下若干网络逆问题的研究
|
摘要
网络优化问题是一类重要的组合优化问题,它要求找到给定问题的最优解。随着社会生产的发展,又产生一些所谓的网络优化逆问题,在这些问题中,先给定一个可行解,但就目前的参数而言,它并不是最优解,我们需要通过尽可能少的修改相应的参数从而使得所给的可行解成为最优解。随着计算机科学、管理科学和现代化生产技术等的日益发展,这类问题与日俱增,越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视。本文就是针对这些新问题,主要对哈明距离下的若干网络逆问题进行了研究。全文共分为四章,第一章主要介绍与组合优化问题及逆问题相关的一些概念和预备知识。接着我们分别研究了不同问题的若干模型。
第二章研究的是赋权哈明距离下最大流逆问题:对给定的连通有向网络N(V,A,c),每条弧都有一个容量改造费用,令f~0是网络N的一个可行流,如何改变网络弧上的容量使得f~0成为新容量下的最大流,且在哈明距离下产生的改造费用最小。我们总共研究了四种模型:对于总和型,我们把问题转化为求解剩余网络的一个受限制割,从而给出了时间复杂性为O(n~3)的多项式时间算法。对于瓶颈型,我们通过把问题转化为求解剩余网络的一个受限制瓶颈割问题,从而给出了时间复杂性为O(m+n·logn)的多项式时间算法。对于两种混合型,我们利用二分法思想,结合前面的算法,分别给出了时间复杂性为O(n~3·logm)和O(n~3)的多项式时间算法。
第三章研究的是赋权哈明距离下最小—最大支撑树逆问题:对给定的连通图G=(V,E,c),每条边都有一个长度改造费用,令T~0是图G的一个支撑树,如何改变图上边的长度使得T~0成为新长度下的最小—最大支撑树,且在哈明距离下产生的改造费用最小。我们总共研究了四种模型:对于总和型,我们先给出了最优解的可能取值,然后通过求解图的受限最小割问题给出了时间复杂性为O(n~4)的多项式时间算法。对于瓶颈型,我们通过求解图的受限最小瓶颈割问题给出了时间复杂性为O(n~5)的多项式时间算法。对于两种混合型,我们利用二分法的思想,结合前面的算法,分别给出了时间复杂性为O(n~5)和O(n~4)的多项式时间算法。
第四章研究的是赋权哈明距离下最小割逆问题:对给定的连通有向网络N(V,A,c),每条弧都有一个容量改造费用,令{X~0,(?)~0}是网络N的一个s-t割,如何改变网络弧上的容量使得{X~0,(?)~0}成为新容量下的最小割,且在哈明距离下产生的改造费用最小。我们研究了两种模型:对于总和型,我们利用背包问题的实例的多项式归约,证明了该问题是NP-难的,对于瓶颈型,通过利用最大流—最小割和哈明距离的性质,我们给出了时间复杂性为O(m·n~3)的多项式时间算法。
Network optimization is one important branch of the combinatorial optimization, the goal is to find an optimal solution of the given problem. As the society advances, the inverse problems of network optimization arise. In these problems, a feasible solution is given which is not optimal under the current parameter values. And it is required to modify some parameters with minimum modification cost such that the given feasible solution forms an optimal solution. This inverse problem becomes increasingly conspicuous, attracting more and more attention from many disciplines, such as operations research, applied mathematics, computer science, management science and so on, as the computer science, the management science and the modem production technology develop. This thesis is organized into four chapters, and mainly deals with the inverse network problems under the weighted Hamming distance. In Chapter 1, we introduce some related basic concepts and knowledge. And then we discuss different models for the different problems.
In Chapter 2, the inverse maximum flow problems under the weighted Hamming distance are discussed. In a given connected and directed network N(V,A,c), each arc has a specific modification cost. Let f~0 be a feasible flow of N. We are asked to modify the arc capacities such that f~0 forms a maximum flow of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we resort to the method of the minimum cut of the residual network, to produce a polynomial algorithm which runs in O(n~3) time. In the bottleneck-type model, the method of the bottleneck minimum cut of the residual network is used to present a polynomial algorithm which runs in O(m + n·log n) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~3·log m) time and O(n~3) time, respectively.
In Chapter 3, we consider the following inverse min-max spanning tree problems under the weighted Hamming distance. In a given connected graph G(V. E. c), each arc has a specific modification cost. Let T~0 be a spanning tree of G. We are asked to modify the edge lengths such that T~0 forms a min-max spanning tree of G and the modification cost of modified edges is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we are first given the range of the value, and use the method of the restricted minimum weight edge cut problem to produce a polynomial algorithm which runs in O(n~4) time. In the bottleneck-type model, the method for the restricted minimum bottleneck-type weight edge cut problem is adopted to present a polynomial algorithm which runs in O(n~5) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~5) time and O(n~4) time, respectively.
In Chapter 4, we consider the following inverse minimum cut problems under the weighted Hamming distance. In a given connected and directed network N(V, A, c), each arc has a specific modification cost. Let {X~0,(X|-)~0 } be an s - t cut of N. We are asked to modify the arc capacities such that {X~0, (X|-)~0 } forms a minimum cut of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Two models are studied. The first is a sum-type model, in which we show the problem is NP-hard by using the reduction from an instance of Knapsack Problem to an instance of the problem in polynomial time. In the latter bottleneck-type model, in terms of the properties of the maximum flow and minimum cut theory and the Hamming distance, we present a polynomial algorithm which runs in O(m·n~3) time.
第二章研究的是赋权哈明距离下最大流逆问题:对给定的连通有向网络N(V,A,c),每条弧都有一个容量改造费用,令f~0是网络N的一个可行流,如何改变网络弧上的容量使得f~0成为新容量下的最大流,且在哈明距离下产生的改造费用最小。我们总共研究了四种模型:对于总和型,我们把问题转化为求解剩余网络的一个受限制割,从而给出了时间复杂性为O(n~3)的多项式时间算法。对于瓶颈型,我们通过把问题转化为求解剩余网络的一个受限制瓶颈割问题,从而给出了时间复杂性为O(m+n·logn)的多项式时间算法。对于两种混合型,我们利用二分法思想,结合前面的算法,分别给出了时间复杂性为O(n~3·logm)和O(n~3)的多项式时间算法。
第三章研究的是赋权哈明距离下最小—最大支撑树逆问题:对给定的连通图G=(V,E,c),每条边都有一个长度改造费用,令T~0是图G的一个支撑树,如何改变图上边的长度使得T~0成为新长度下的最小—最大支撑树,且在哈明距离下产生的改造费用最小。我们总共研究了四种模型:对于总和型,我们先给出了最优解的可能取值,然后通过求解图的受限最小割问题给出了时间复杂性为O(n~4)的多项式时间算法。对于瓶颈型,我们通过求解图的受限最小瓶颈割问题给出了时间复杂性为O(n~5)的多项式时间算法。对于两种混合型,我们利用二分法的思想,结合前面的算法,分别给出了时间复杂性为O(n~5)和O(n~4)的多项式时间算法。
第四章研究的是赋权哈明距离下最小割逆问题:对给定的连通有向网络N(V,A,c),每条弧都有一个容量改造费用,令{X~0,(?)~0}是网络N的一个s-t割,如何改变网络弧上的容量使得{X~0,(?)~0}成为新容量下的最小割,且在哈明距离下产生的改造费用最小。我们研究了两种模型:对于总和型,我们利用背包问题的实例的多项式归约,证明了该问题是NP-难的,对于瓶颈型,通过利用最大流—最小割和哈明距离的性质,我们给出了时间复杂性为O(m·n~3)的多项式时间算法。
Network optimization is one important branch of the combinatorial optimization, the goal is to find an optimal solution of the given problem. As the society advances, the inverse problems of network optimization arise. In these problems, a feasible solution is given which is not optimal under the current parameter values. And it is required to modify some parameters with minimum modification cost such that the given feasible solution forms an optimal solution. This inverse problem becomes increasingly conspicuous, attracting more and more attention from many disciplines, such as operations research, applied mathematics, computer science, management science and so on, as the computer science, the management science and the modem production technology develop. This thesis is organized into four chapters, and mainly deals with the inverse network problems under the weighted Hamming distance. In Chapter 1, we introduce some related basic concepts and knowledge. And then we discuss different models for the different problems.
In Chapter 2, the inverse maximum flow problems under the weighted Hamming distance are discussed. In a given connected and directed network N(V,A,c), each arc has a specific modification cost. Let f~0 be a feasible flow of N. We are asked to modify the arc capacities such that f~0 forms a maximum flow of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we resort to the method of the minimum cut of the residual network, to produce a polynomial algorithm which runs in O(n~3) time. In the bottleneck-type model, the method of the bottleneck minimum cut of the residual network is used to present a polynomial algorithm which runs in O(m + n·log n) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~3·log m) time and O(n~3) time, respectively.
In Chapter 3, we consider the following inverse min-max spanning tree problems under the weighted Hamming distance. In a given connected graph G(V. E. c), each arc has a specific modification cost. Let T~0 be a spanning tree of G. We are asked to modify the edge lengths such that T~0 forms a min-max spanning tree of G and the modification cost of modified edges is minimized under the weighted Hamming distance. Four models are studied. In the sum-type model, we are first given the range of the value, and use the method of the restricted minimum weight edge cut problem to produce a polynomial algorithm which runs in O(n~4) time. In the bottleneck-type model, the method for the restricted minimum bottleneck-type weight edge cut problem is adopted to present a polynomial algorithm which runs in O(n~5) time. And as for the model of two mixed types, using the bisection method and the algorithms given before, we present their polynomial algorithms that run in O(n~5) time and O(n~4) time, respectively.
In Chapter 4, we consider the following inverse minimum cut problems under the weighted Hamming distance. In a given connected and directed network N(V, A, c), each arc has a specific modification cost. Let {X~0,(X|-)~0 } be an s - t cut of N. We are asked to modify the arc capacities such that {X~0, (X|-)~0 } forms a minimum cut of N and the modification cost of modified arcs is minimized under the weighted Hamming distance. Two models are studied. The first is a sum-type model, in which we show the problem is NP-hard by using the reduction from an instance of Knapsack Problem to an instance of the problem in polynomial time. In the latter bottleneck-type model, in terms of the properties of the maximum flow and minimum cut theory and the Hamming distance, we present a polynomial algorithm which runs in O(m·n~3) time.
引文
[1] R.K. Ahuja, Th.L. Magnanti and J.B. Orlin, Network Flows. Theory, Algorithms, and Applications, Prentice, Hall Inc.: Englewood Cliffs, NJ, 1993.
[2] R.K. Ahuja and J.B. Orlin, A faster algorithm for the inverse spanning tree problem, J. Algorithms, 34, 177- 193,2000.
[3] R.K. Ahuja and J.B. Orlin, Inverse optimization, Open Res., 49, 771 - 783, 2001.
[4] R.K. Ahuja and J.B. Orlin, Combinatorial algorithms for inverse network flow problems, Networks, 40(4), 181 - 187,2002.
[51 C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. U.S.A., 43, 842 - 844, 1957.
[6] O. Berman, D.I. Ingco and A. Odoni, Improving the location of minisum facilities through network modification, Ann. Oper. Res., 40, 1 - 16, 1992.
[7] O. Berman, D.I. Ingco and A. Odoni, Improving the location of minimax facilities through network modification, Networks, 24, 31 - 41, 1994.
[8] R.E. Burkard, B. Klinz and J. Zhang, Bottleneck capacity expansion problems with general budget constraints, RAIRO Oper. Res., 35, 1 - 20, 2001.
[9] R.E. Burkard, Y. Lin and J. Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res., 153(1), 191 - 199, 2004.
[10] R.E. Burkard, C. Pleschiutschnig and J. Zhang, Inverse median problems, Discrete Optimization, 1, 23 - 39, 2004.
[11] D. Burton, W.R. Pulleyblank and Ph.L. Toint, The inverse shortest paths problem with upper bounds on shortest paths costs, in Network optimization Gainesville, FL, 1996, 156 - 171. Springer: Berlin, 1997.
[12] D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Programming, 53, 45 - 61, 1992.
[13] D. Burton and Ph. L. Toint, On the use of an inverse shortest paths algorithm for recovering linearly correlated costs, Math. Programming, 63, 1 - 22, 1992.
[14] M.C. Cai, Inverse problems of matroid intersection, J. Comb. Optim., 3, 465 - 474, 1999.
[15] M.C. Cai and Y. Li, Inverse matroid intersection problem, Math. Methods Oper. Res., 45, 235-243, 1997.
[16]M.C.Cai and X.G.Yang,Inverse shortest path problems,in Operations Research and its Applications.First International Symposium,ISORA'95,Beijing,P.R.China,August 19-22,1995.
D.Z.Du,X.S.Zhang,and K.Cheng(eds.),Proceedings of Lecture Notes in Operations Research,Beijing World Publishing Corporation,1,242-248,1995.
[17]M.C.Cai,X.G.Yang and Y.Li.Inverse polymatroidal flow problem,J.Comb.Optim.,3,115-126,1999.
[18]M.C.Cai,X.G.Yang and Y.Li,Inverse problems of submodular functions on digraphs,J.Optim.Theory Appl.,104,559-575,2000.
[19]M.C.Cai,X.G.Yang and J.Z.Zhang,The complexity analysis of the inverse center location problem,J.Global Optim.,15,213-218,1999.
[20]P.M.Camerini,The min-max spanning tree problem and some extensions,Information Processing Letters,7,10-14,1978.
[21]M.Dell'Amico,F.Maffioli and F.Malucelli,The base-matroid and inverse combinatorial optimization problems,Discrete Appl.Math.,128,337-353,2003.
[22]R.B.Dial,Minimal-revenue congestion pricing Part Ⅰ:A fast algorithm for the single-origin case,Transportation Res.Part B,33,189-202,1999.
[23]R.B.Dial,Minimal-revenue congestion pricing Part Ⅱ:An efficient algorithm for the general case,Transportation Res.Part B,34,645-665,2000.
[24]K.U.Drangmeister,S.O.Krumke,M.V.Marathe,H.Noltemeier and S.S.Ravi,Modifying edges of a network to obtain short subgraphs,Theoret.Comput.Sci.,203,91-121,1998.
[25]C.W.Duin and A.Volgenant,Some inverse optimization problems under the Hamming distance,European Journal of Operational Research,170,887-899,2006.
[26]J.Edmonds and R.Giles,A min-max relation for submodular functions on graphs,in Studies in Integer Programming(Proc.Workshop,Bonn,1975),of Ann.of Discrete Math.,North-Holland:Amsterdam,1,185-204,1977.
[27]H.W.Engl,M.Hanke and A.Neubauer,Regularization of Inverse Problems,Kluwer Academic Publishers Group:Dordrecht,1996.
[28]S.P.Fekete,W.Hochstattler,St.Kromberg and Ch.Moll,The complexity of an inverse shortest paths problem,in Contemporary trends in discrete mathematics(Stirin Castle,1997),Amer.Math.Soc.,Providence,RI,113-127,1999.
[29]A.Frank,A weighted matroid intersection algorithm,J.Algorithms,2,328-336,1981.
[30]A.Frank,An algorithm for submodular functions on graphs,in Bonn Workshop on Combinatorial Optimization(Bonn,1980),North-Holland:Amsterdam,97-120,1982.
[31]A.Frank,Packing paths,circuits,and cuts-a survey,in Paths,flows,and VLSI-layout(Bonn,1988),Springer,Berlin,47-100,1990.
[32]G.N.Frederickson and R.Solis-Oba,Efficient algorithms for robustness in matroid optimization,in Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans,LA,1997),ACM:New York,659-668,1997.
[33]G.N.Frederickson and R.Solis-Oba,Increasing the weight of minimum spanning trees,J.Algorithms,33,244-266,1999.
[34]D.R.Fulkerson and G.C.Harding,Maximizing the minimum source-sink path subject to a budget constraint,Math.Programming,13,116-118,1977.
[35]M.R.Garey and D.S.Johnson.Computers and Intractability:A Guide to the Theory of NP-Completeness.Freeman,San Francisco,1979.
[36]D.Goldfarb and A.Idnani,A numerically stable dual method for solving strictly convex quadratic programs,Math.Programming,27,1-33,1983.
[37]M.Grotschel,L.Lovasz and A.Schrijver,Geometric Algorithms and Combinatorial Optimization,2nd edn.Springer-Verlag:Berlin,1993.
[38]X.Guan and J.Z.Zhang,Inverse Bottleneck Optimization Problems under Weighted Hamming Distance,Lecture Notes in Computer Science,4041,220-230,2006.
[39]S.Hakimi,Optimum locations of switching centers and the absolute centers and medians of a graph,Oper.Res.,12,450-459,1964.
[40]R.Hassin,Minimum cost flow with set-constraints,Networks,12,1-21,1982.
[41]Y.He,B.W.Zhang and E.Y.Yao,Wighted inverse minimum spanning tree problems under Hamming distance,Journal of Combinatorial Optimization,9(1),91-100,2005.
[42]C.Heuberger,Inverse Optimization:A survey on problems,methods,and results,Journal of Combinatorial Optimization,8,329-361,2004.
[43]D.S.Hochbaum.Approximation algorithms for NP-Hard Problems.PWS Publishing Company,1997.
[44]D.S.Hochbaum,Efficient algorithms for the inverse spanning-tree problem,Oper.Res.,51(5),785-797,2003.
[45] Z. Hu and Z. Liu, A strongly polynomial algorithm for the inverse shortest arborescence problem, Discrete Appl. Math., 82, 135 - 154, 1998.
[46] S. Huang and Z. Liu, On the inverse problem of linear programming and its application to minimum weight perfect k-matching, Eur. J. Oper. Res., 112, 421 - 426, 1999.
[47] S.O. Krumke, M.V.Marathe, H. Noltemeier,R.Ravi and S.S. Ravi, Approximation algorithms for certain network improvement problems, J. Comb. Optim., 2, 257 - 288, 1998.
[48] E.L. Lawler and C.U. Martel, Computing maximal "polymatroidal" network flows, Math. Oper. Res., 7,334 -347, 1982.
[49] L.C. Liu and Q. Wang, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, Journal of Global Optimization, 43(1), 83-95, 2009.
[50] L.C. Liu and E.Y. Yao, A weighted inverse minimum cut problem under the bottleneck type hamming distance, Asia-Pacific Journal of Operational Research, 24(5), 725-736, 2007.
[51] L.C. Liu and E.Y. Yao, Inverse min-max spanning tree problem under the Weighted sum-type Hamming distance, Theoretical Computer Science , 396, 28-34, 2008.
[52] L.C. Liu and J.Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12, 395-408, 2006.
[53] Z. Liu and J. Zhang, On inverse problems of optimum perfect matching, J. Comb. Optim., 7(3), 215 - 228, 2003.
[54] B. Marlow, Inverse problems, http://www.inverse-problems.com/.
[55] T.J. Moser, Shortest paths calculation of seismic rays, Geophysics, 56, 59 - 67, 1991.
[56] G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, John Wiley and Sons Inc.: New York, 1988.
[57] C. Phillips, The network inhibition problem, in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993, San Diego, CA USA, May 16- 18, 776 - 785, 1993.
[58] T. Radzik, Parametric flows, weighted means of cuts, and fractional combinatorial optimization, in Complexity in Numerical Optimization, World Sci. Publishing: River Edge, NJ, 351 -386, 1993.
[59] A. Schrijver, Total dual integrality from directed graphs, crossing families, and sub- and su-permodular functions, in Progress in Combinatorial Optimization Waterloo, Ont., 1982, Academic Press: Toronto, Ont., 315-361, 1984.
[60]A.Schrijver,Theory of Linear and Integer Programming,John Wiley and Sons Ltd.:Chichester,1986.
[61]A.Schrijver,Combinatorial Optimization,Polyhedra and Efficiency,Springer-Verlag,Berlin,2003.
[62]P.T.Sokkalingam,The minimum cost flow problem:Primal algorithms and cost perturbations,Unpublished dissertation,Department of Mathematics,Indian Institute of Technology,Kanpur,India,1995.
[63]P.T.Sokkalingam,R.K.Ahuja and J.B.Orlin,Solving inverse spanning tree problems through network flow techniques,Oper.Res.,47,291-298,1999.
[64]E.Tardos,A strongly polynomial algorithm to solve combinatorial linear programs,Oper.Res.,34,250-256,1986.
[65]Q.Wei,J.Zhang,and X.Zhang,An inverse DEA model for inputs/outputs estimate,Eur.J.Oper.Res.,121,151-163,2000.
[66]W.L.Winston,Operations Research:Applications and Algorithms,3rd edn.Duxbury Press:Boston,MA,1993.
[67]S.Xu and J.Zhang,An inverse problem of the weighted shortest path problem,Japan J.Indust.Appl.Math.,12,47-59,1995.
[68]C.Yang,Some inverse optimization problems and extensions,PhD Thesis,Department of Mathematics,City University of Hong Kong,1997.
[69]C.Yang and J.Zhang,A constrained capacity expansion problem on networks,Int.J.Comput.Math.,70,19-33,1998.
[70]C.Yang and J.Zhang,Inverse maximum capacity problems,OR Spektrum,20,97-100,1998.
[71]C.Yang and J.Zhang,Two general methods for inverse optimization problems,Appl.Math.Lett.,12,69-72,1999.
[72]C.Yang,J.Zhang and Z.Ma,Inverse maximum flow and minimum cut problems,Optimization,40,147-170,1997.
[73]X.G.Yang,Complexity of partial inverse assignment problem and partial inverse cut problem,RAIRO Oper.Res.,35,1,117-126,2001.
[74]X.G.Yang and J.Z.Zhang,Sone new results on inverse sorting problems.Lecture Notes in Computer Science,3595,985-992,2005.
[75]X.G.Yang and J.Z.Zhang,Some inverse min-max network problems under weighted l_1 and l_∞ norms with bound constraints on changes,Journal of Combinatorial Optimization,13,123-135,2007.
[76]姚恩瑜,何勇,陈仕平.数学规划与组合优化,浙江大学出版社,2001.
[77]B.W.Zhang,J.Z.Zhang and Y.He,The center location improvement problem under the Hamming distance,Journal of Combinatorial Optimization,9(2),187-198,2005.
[78]B.W.Zhang,J.Z.Zhang and Y.He,Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance,Journal of Global Optimization,34(3),467-474,2006.
[79]B.W.Zhang,J.Z.Zhang and L.Q.Qi,The shortest path improvement problems under Hamming distance,Journal of Combinatorial Optimization,12(4),351-361,2006.
[80]J.Zhang and M.C.Cai,Inverse problem of minimum cuts,Math.Methods Oper.Res.,47,51-58,1998.
[81]J.Zhang and Z.Liu,Calculating some inverse linear programming problems,J.Comput.Appl.Math.,72,261-273,1996.
[82]J.Zhang and Z.Liu,A further study on inverse linear programming problems,J.Comput.Appl.Math.,106,345-359,1999.
[83]J.Zhang and Z.Liu,A general model of some inverse optimization problems and its solution method under l_∞ norm,J.Comb.Optim.,6,207-227,2002.
[84]J.Zhang and Z.Liu,An oracle strongly polynomial algorithm for bottleneck expansion problems,Optimization Methods and Software,17,61-75,2002.
[85]J.Zhang,Z.Liu and Z.Ma,On the inverse problem of minimum spanning tree with partition constraints,Math.Methods Oper.Res.,44,171-187,1996.
[86]J.Zhang,Z.Liu and Z.Ma,The inverse fractional matching problem,J.Austral.Math.Soc.Ser.B,40,484-496,1999.
[87]J.Zhang,Z.Liu and Z.Ma,Some reverse location problems,Eur.J.Oper.Res.,124,77-88,2000.
[88]J.Zhang and Z.Ma,A network flow method for solving some inverse combinatorial optimization problems,Optimization,37,59-72,1996.
[89]J.Zhang and Z.Ma,Solution structure of some inverse combinatorial optimization problems,J.Comb.Optim.,3,127-139,1999.
[90]J.Zhang,Z.Ma and C.Yang,A column generation method for inverse shortest path problems,ZOR—Math.Methods Oper.Res.,41,347-358,1995.
[91]J.Zhang,S.Xu and Z.Ma,An algorithm for inverse minimum spanning tree problem,Optim.Methods Softw.,8,69-84,1997.
[92]J.Zhang,X.G.Yang and M.C.Cai,Reverse center location problem,in A.Aggarwal and C.Pandu Rangan,editors,Algorithms and computation,10th International Symposium,ISAAC' 99,Chennai,India,December 16-18,1999.Proceedings,vol.1741 of Lecture Notes in Computer Science,Springer,279-294,1999.
[93]J.Zhang,C.Yang and Y.Lin,A class of bottleneck expansion problems,Computers and Operations Research,28,505-519,2001.
[2] R.K. Ahuja and J.B. Orlin, A faster algorithm for the inverse spanning tree problem, J. Algorithms, 34, 177- 193,2000.
[3] R.K. Ahuja and J.B. Orlin, Inverse optimization, Open Res., 49, 771 - 783, 2001.
[4] R.K. Ahuja and J.B. Orlin, Combinatorial algorithms for inverse network flow problems, Networks, 40(4), 181 - 187,2002.
[51 C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. U.S.A., 43, 842 - 844, 1957.
[6] O. Berman, D.I. Ingco and A. Odoni, Improving the location of minisum facilities through network modification, Ann. Oper. Res., 40, 1 - 16, 1992.
[7] O. Berman, D.I. Ingco and A. Odoni, Improving the location of minimax facilities through network modification, Networks, 24, 31 - 41, 1994.
[8] R.E. Burkard, B. Klinz and J. Zhang, Bottleneck capacity expansion problems with general budget constraints, RAIRO Oper. Res., 35, 1 - 20, 2001.
[9] R.E. Burkard, Y. Lin and J. Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res., 153(1), 191 - 199, 2004.
[10] R.E. Burkard, C. Pleschiutschnig and J. Zhang, Inverse median problems, Discrete Optimization, 1, 23 - 39, 2004.
[11] D. Burton, W.R. Pulleyblank and Ph.L. Toint, The inverse shortest paths problem with upper bounds on shortest paths costs, in Network optimization Gainesville, FL, 1996, 156 - 171. Springer: Berlin, 1997.
[12] D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Programming, 53, 45 - 61, 1992.
[13] D. Burton and Ph. L. Toint, On the use of an inverse shortest paths algorithm for recovering linearly correlated costs, Math. Programming, 63, 1 - 22, 1992.
[14] M.C. Cai, Inverse problems of matroid intersection, J. Comb. Optim., 3, 465 - 474, 1999.
[15] M.C. Cai and Y. Li, Inverse matroid intersection problem, Math. Methods Oper. Res., 45, 235-243, 1997.
[16]M.C.Cai and X.G.Yang,Inverse shortest path problems,in Operations Research and its Applications.First International Symposium,ISORA'95,Beijing,P.R.China,August 19-22,1995.
D.Z.Du,X.S.Zhang,and K.Cheng(eds.),Proceedings of Lecture Notes in Operations Research,Beijing World Publishing Corporation,1,242-248,1995.
[17]M.C.Cai,X.G.Yang and Y.Li.Inverse polymatroidal flow problem,J.Comb.Optim.,3,115-126,1999.
[18]M.C.Cai,X.G.Yang and Y.Li,Inverse problems of submodular functions on digraphs,J.Optim.Theory Appl.,104,559-575,2000.
[19]M.C.Cai,X.G.Yang and J.Z.Zhang,The complexity analysis of the inverse center location problem,J.Global Optim.,15,213-218,1999.
[20]P.M.Camerini,The min-max spanning tree problem and some extensions,Information Processing Letters,7,10-14,1978.
[21]M.Dell'Amico,F.Maffioli and F.Malucelli,The base-matroid and inverse combinatorial optimization problems,Discrete Appl.Math.,128,337-353,2003.
[22]R.B.Dial,Minimal-revenue congestion pricing Part Ⅰ:A fast algorithm for the single-origin case,Transportation Res.Part B,33,189-202,1999.
[23]R.B.Dial,Minimal-revenue congestion pricing Part Ⅱ:An efficient algorithm for the general case,Transportation Res.Part B,34,645-665,2000.
[24]K.U.Drangmeister,S.O.Krumke,M.V.Marathe,H.Noltemeier and S.S.Ravi,Modifying edges of a network to obtain short subgraphs,Theoret.Comput.Sci.,203,91-121,1998.
[25]C.W.Duin and A.Volgenant,Some inverse optimization problems under the Hamming distance,European Journal of Operational Research,170,887-899,2006.
[26]J.Edmonds and R.Giles,A min-max relation for submodular functions on graphs,in Studies in Integer Programming(Proc.Workshop,Bonn,1975),of Ann.of Discrete Math.,North-Holland:Amsterdam,1,185-204,1977.
[27]H.W.Engl,M.Hanke and A.Neubauer,Regularization of Inverse Problems,Kluwer Academic Publishers Group:Dordrecht,1996.
[28]S.P.Fekete,W.Hochstattler,St.Kromberg and Ch.Moll,The complexity of an inverse shortest paths problem,in Contemporary trends in discrete mathematics(Stirin Castle,1997),Amer.Math.Soc.,Providence,RI,113-127,1999.
[29]A.Frank,A weighted matroid intersection algorithm,J.Algorithms,2,328-336,1981.
[30]A.Frank,An algorithm for submodular functions on graphs,in Bonn Workshop on Combinatorial Optimization(Bonn,1980),North-Holland:Amsterdam,97-120,1982.
[31]A.Frank,Packing paths,circuits,and cuts-a survey,in Paths,flows,and VLSI-layout(Bonn,1988),Springer,Berlin,47-100,1990.
[32]G.N.Frederickson and R.Solis-Oba,Efficient algorithms for robustness in matroid optimization,in Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans,LA,1997),ACM:New York,659-668,1997.
[33]G.N.Frederickson and R.Solis-Oba,Increasing the weight of minimum spanning trees,J.Algorithms,33,244-266,1999.
[34]D.R.Fulkerson and G.C.Harding,Maximizing the minimum source-sink path subject to a budget constraint,Math.Programming,13,116-118,1977.
[35]M.R.Garey and D.S.Johnson.Computers and Intractability:A Guide to the Theory of NP-Completeness.Freeman,San Francisco,1979.
[36]D.Goldfarb and A.Idnani,A numerically stable dual method for solving strictly convex quadratic programs,Math.Programming,27,1-33,1983.
[37]M.Grotschel,L.Lovasz and A.Schrijver,Geometric Algorithms and Combinatorial Optimization,2nd edn.Springer-Verlag:Berlin,1993.
[38]X.Guan and J.Z.Zhang,Inverse Bottleneck Optimization Problems under Weighted Hamming Distance,Lecture Notes in Computer Science,4041,220-230,2006.
[39]S.Hakimi,Optimum locations of switching centers and the absolute centers and medians of a graph,Oper.Res.,12,450-459,1964.
[40]R.Hassin,Minimum cost flow with set-constraints,Networks,12,1-21,1982.
[41]Y.He,B.W.Zhang and E.Y.Yao,Wighted inverse minimum spanning tree problems under Hamming distance,Journal of Combinatorial Optimization,9(1),91-100,2005.
[42]C.Heuberger,Inverse Optimization:A survey on problems,methods,and results,Journal of Combinatorial Optimization,8,329-361,2004.
[43]D.S.Hochbaum.Approximation algorithms for NP-Hard Problems.PWS Publishing Company,1997.
[44]D.S.Hochbaum,Efficient algorithms for the inverse spanning-tree problem,Oper.Res.,51(5),785-797,2003.
[45] Z. Hu and Z. Liu, A strongly polynomial algorithm for the inverse shortest arborescence problem, Discrete Appl. Math., 82, 135 - 154, 1998.
[46] S. Huang and Z. Liu, On the inverse problem of linear programming and its application to minimum weight perfect k-matching, Eur. J. Oper. Res., 112, 421 - 426, 1999.
[47] S.O. Krumke, M.V.Marathe, H. Noltemeier,R.Ravi and S.S. Ravi, Approximation algorithms for certain network improvement problems, J. Comb. Optim., 2, 257 - 288, 1998.
[48] E.L. Lawler and C.U. Martel, Computing maximal "polymatroidal" network flows, Math. Oper. Res., 7,334 -347, 1982.
[49] L.C. Liu and Q. Wang, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, Journal of Global Optimization, 43(1), 83-95, 2009.
[50] L.C. Liu and E.Y. Yao, A weighted inverse minimum cut problem under the bottleneck type hamming distance, Asia-Pacific Journal of Operational Research, 24(5), 725-736, 2007.
[51] L.C. Liu and E.Y. Yao, Inverse min-max spanning tree problem under the Weighted sum-type Hamming distance, Theoretical Computer Science , 396, 28-34, 2008.
[52] L.C. Liu and J.Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12, 395-408, 2006.
[53] Z. Liu and J. Zhang, On inverse problems of optimum perfect matching, J. Comb. Optim., 7(3), 215 - 228, 2003.
[54] B. Marlow, Inverse problems, http://www.inverse-problems.com/.
[55] T.J. Moser, Shortest paths calculation of seismic rays, Geophysics, 56, 59 - 67, 1991.
[56] G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, John Wiley and Sons Inc.: New York, 1988.
[57] C. Phillips, The network inhibition problem, in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993, San Diego, CA USA, May 16- 18, 776 - 785, 1993.
[58] T. Radzik, Parametric flows, weighted means of cuts, and fractional combinatorial optimization, in Complexity in Numerical Optimization, World Sci. Publishing: River Edge, NJ, 351 -386, 1993.
[59] A. Schrijver, Total dual integrality from directed graphs, crossing families, and sub- and su-permodular functions, in Progress in Combinatorial Optimization Waterloo, Ont., 1982, Academic Press: Toronto, Ont., 315-361, 1984.
[60]A.Schrijver,Theory of Linear and Integer Programming,John Wiley and Sons Ltd.:Chichester,1986.
[61]A.Schrijver,Combinatorial Optimization,Polyhedra and Efficiency,Springer-Verlag,Berlin,2003.
[62]P.T.Sokkalingam,The minimum cost flow problem:Primal algorithms and cost perturbations,Unpublished dissertation,Department of Mathematics,Indian Institute of Technology,Kanpur,India,1995.
[63]P.T.Sokkalingam,R.K.Ahuja and J.B.Orlin,Solving inverse spanning tree problems through network flow techniques,Oper.Res.,47,291-298,1999.
[64]E.Tardos,A strongly polynomial algorithm to solve combinatorial linear programs,Oper.Res.,34,250-256,1986.
[65]Q.Wei,J.Zhang,and X.Zhang,An inverse DEA model for inputs/outputs estimate,Eur.J.Oper.Res.,121,151-163,2000.
[66]W.L.Winston,Operations Research:Applications and Algorithms,3rd edn.Duxbury Press:Boston,MA,1993.
[67]S.Xu and J.Zhang,An inverse problem of the weighted shortest path problem,Japan J.Indust.Appl.Math.,12,47-59,1995.
[68]C.Yang,Some inverse optimization problems and extensions,PhD Thesis,Department of Mathematics,City University of Hong Kong,1997.
[69]C.Yang and J.Zhang,A constrained capacity expansion problem on networks,Int.J.Comput.Math.,70,19-33,1998.
[70]C.Yang and J.Zhang,Inverse maximum capacity problems,OR Spektrum,20,97-100,1998.
[71]C.Yang and J.Zhang,Two general methods for inverse optimization problems,Appl.Math.Lett.,12,69-72,1999.
[72]C.Yang,J.Zhang and Z.Ma,Inverse maximum flow and minimum cut problems,Optimization,40,147-170,1997.
[73]X.G.Yang,Complexity of partial inverse assignment problem and partial inverse cut problem,RAIRO Oper.Res.,35,1,117-126,2001.
[74]X.G.Yang and J.Z.Zhang,Sone new results on inverse sorting problems.Lecture Notes in Computer Science,3595,985-992,2005.
[75]X.G.Yang and J.Z.Zhang,Some inverse min-max network problems under weighted l_1 and l_∞ norms with bound constraints on changes,Journal of Combinatorial Optimization,13,123-135,2007.
[76]姚恩瑜,何勇,陈仕平.数学规划与组合优化,浙江大学出版社,2001.
[77]B.W.Zhang,J.Z.Zhang and Y.He,The center location improvement problem under the Hamming distance,Journal of Combinatorial Optimization,9(2),187-198,2005.
[78]B.W.Zhang,J.Z.Zhang and Y.He,Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance,Journal of Global Optimization,34(3),467-474,2006.
[79]B.W.Zhang,J.Z.Zhang and L.Q.Qi,The shortest path improvement problems under Hamming distance,Journal of Combinatorial Optimization,12(4),351-361,2006.
[80]J.Zhang and M.C.Cai,Inverse problem of minimum cuts,Math.Methods Oper.Res.,47,51-58,1998.
[81]J.Zhang and Z.Liu,Calculating some inverse linear programming problems,J.Comput.Appl.Math.,72,261-273,1996.
[82]J.Zhang and Z.Liu,A further study on inverse linear programming problems,J.Comput.Appl.Math.,106,345-359,1999.
[83]J.Zhang and Z.Liu,A general model of some inverse optimization problems and its solution method under l_∞ norm,J.Comb.Optim.,6,207-227,2002.
[84]J.Zhang and Z.Liu,An oracle strongly polynomial algorithm for bottleneck expansion problems,Optimization Methods and Software,17,61-75,2002.
[85]J.Zhang,Z.Liu and Z.Ma,On the inverse problem of minimum spanning tree with partition constraints,Math.Methods Oper.Res.,44,171-187,1996.
[86]J.Zhang,Z.Liu and Z.Ma,The inverse fractional matching problem,J.Austral.Math.Soc.Ser.B,40,484-496,1999.
[87]J.Zhang,Z.Liu and Z.Ma,Some reverse location problems,Eur.J.Oper.Res.,124,77-88,2000.
[88]J.Zhang and Z.Ma,A network flow method for solving some inverse combinatorial optimization problems,Optimization,37,59-72,1996.
[89]J.Zhang and Z.Ma,Solution structure of some inverse combinatorial optimization problems,J.Comb.Optim.,3,127-139,1999.
[90]J.Zhang,Z.Ma and C.Yang,A column generation method for inverse shortest path problems,ZOR—Math.Methods Oper.Res.,41,347-358,1995.
[91]J.Zhang,S.Xu and Z.Ma,An algorithm for inverse minimum spanning tree problem,Optim.Methods Softw.,8,69-84,1997.
[92]J.Zhang,X.G.Yang and M.C.Cai,Reverse center location problem,in A.Aggarwal and C.Pandu Rangan,editors,Algorithms and computation,10th International Symposium,ISAAC' 99,Chennai,India,December 16-18,1999.Proceedings,vol.1741 of Lecture Notes in Computer Science,Springer,279-294,1999.
[93]J.Zhang,C.Yang and Y.Lin,A class of bottleneck expansion problems,Computers and Operations Research,28,505-519,2001.