LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

Firdovsi Sharıfov; Hakan Kutucu

LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

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

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.

Details

Primary Language

English

Subjects

Engineering

Journal Section

Research Article

Authors

Firdovsi Sharıfov This is me
0000-0001-8768-3649
Ukraine

Hakan Kutucu This is me
0000-0001-7144-7246
Türkiye

Publication Date

September 1, 2018

Submission Date

April 5, 2017

Acceptance Date

April 11, 2018

Published in Issue

Year 2018 Volume: 36 Number: 3

IZ

https://izlik.org/JA36MC89JP

Cite

RIS / Bibtex

APA

Sharıfov, F., & Kutucu, H. (2018). LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. Sigma Journal of Engineering and Natural Sciences, 36(3), 835-848. https://izlik.org/JA36MC89JP

AMA

1.Sharıfov F, Kutucu H. LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. SIGMA. 2018;36(3):835-848. https://izlik.org/JA36MC89JP

Chicago

Sharıfov, Firdovsi, and Hakan Kutucu. 2018. “LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES”. Sigma Journal of Engineering and Natural Sciences 36 (3): 835-48. https://izlik.org/JA36MC89JP.

EndNote

Sharıfov F, Kutucu H (September 1, 2018) LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. Sigma Journal of Engineering and Natural Sciences 36 3 835–848.

IEEE

[1]F. Sharıfov and H. Kutucu, “LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES”, SIGMA, vol. 36, no. 3, pp. 835–848, Sept. 2018, [Online]. Available: https://izlik.org/JA36MC89JP

ISNAD

Sharıfov, Firdovsi - Kutucu, Hakan. “LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES”. Sigma Journal of Engineering and Natural Sciences 36/3 (September 1, 2018): 835-848. https://izlik.org/JA36MC89JP.

JAMA

1.Sharıfov F, Kutucu H. LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. SIGMA. 2018;36:835–848.

MLA

Sharıfov, Firdovsi, and Hakan Kutucu. “LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES”. Sigma Journal of Engineering and Natural Sciences, vol. 36, no. 3, Sept. 2018, pp. 835-48, https://izlik.org/JA36MC89JP.

Vancouver

1.Firdovsi Sharıfov, Hakan Kutucu. LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. SIGMA [Internet]. 2018 Sep. 1;36(3):835-48. Available from: https://izlik.org/JA36MC89JP