KaydedilenlerDerginizi ekleyin

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

LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

Firdovsi SHARIFOV
Hakan KUTUCU
Sayfa
835–848
Yayın Tarihi
2018-09-01
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

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

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez: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).
📊
Temel Bulgular & Veri:We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = |E|, n = |V|) iterations.
💡
Sonuç & Katkı:We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler: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.

🔖

Bu Makaleye Atıf Yap

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

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (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).