SavedAdd your journal

Journals / Sigma Journal of Engineering and Natural Sciences / 2018 / Cilt: 36 Sayı: 3

LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

Firdovsi SHARIFOV
Hakan KUTUCU
Pages
835–848
Publication Date
2018-09-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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).
📊
Key Findings & Data:We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = |E|, n = |V|) iterations.
💡
Conclusion & Impact:We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Network design · submodular function · fundamental cut sets

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.

🔖

Cite This Article

SHARIFOV, F., KUTUCU, H. (2018). LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. Sigma Journal of Engineering and Natural Sciences, Cilt: 36 Sayı: 3, 835–848. https://ajindex.com/articles/897739

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (14)

  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).