LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

Year 2018, Volume: 36 Issue: 3, 835 - 848, 01.09.2018

Firdovsi Sharıfov Hakan Kutucu

Abstract

In the paper, we consider a linear programming problem with con-straint matrices whose rows are 0, 1 characteristics vectors of fundamental cuts in a given undirected graph G = (V, E). We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = |E|, n = |V|) iterations. We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.

Keywords

Network design, submodular function, fundamental cut sets, linear programming

References

• [1] C. Berge: Balanced matrices and property (G), Mathematical Programming Studies 12 (1980), 163-175.
• [2] K.H. Borgwardt: The simplex method: A probabilistic Analysis, Algorithms and Combinatorics 1, Springer-Verlag, (1987).
• [3] F. Fritzsche and F.B. Holt: More polytope meeting the conjectured Hirsch bound, Discrete Math., 205 (1999), 77-84.
• [4] M.X. Goemans and D.P. Williamson: A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 24:2 (1995), 296-317.
• [5] T.C. Hu: Optimum communication spanning trees, SIAM Journal on Computing, 3:3 (1974), 188-195.
• [6] M. Kaufmann and D. Wagner: Drawing Graphs: Methods and Models, Springer, (2001).
• [7] V. Klee and G.J. Minty: How good is the simplex algorithm?, Inequalities-III, Academic Press, New York (1972), 159-175.
• [8] K.V. Marintseva, F.A. Sharifov, G.N. Yun: A problem of airport capacity definition, Aeronautic, 5 (2013), 1-13.
• [9] J. Oxley: Matroid theory, Oxford University Press, 2nd Ed., New York, (2011).
• [10] Schrijver A.: Combinatorial optimization: Polyhedra and efficiency in Algorithms and Combinatorics, Spinger-Verlag, Berlin, Heidelberg, 24, (2003).
• [11] F.A. Sharifov and L. Hulianytskyi: Models and Complexity of Problems of Design and Reconstruction of Telecommunication and Transport Systems, Cybernetics and Systems Analysis, 50:5 (2014), 693-700.
• [12] P.D. Seymour: Decomposition of Regular Matroids, Journal of Combinatorial Theory, Series B, 28:3 (1980), 305-359.
• [13] M.J. Todd: Polynomial expected behaviour of a pivoting algorithm for linear complementarity and linear programming problems, Technical Report No. 595, School of Operations Research and Industrial Engineering, Cornell University, (Ithaca, NY, November 1983), Mathematical Programming, 35 (1986), 173-192.
• [14] K. Truemper: Matroid Decomposition, Academic Press, (1992).