KaydedilenlerDerginizi ekleyin

Dergiler / An International Journal of Optimization and Control: Theories & Applications (IJOCTA) / 2020 / Cilt: 10 - Sayı: 1

Maximum cut problem: new models

Hakan KUTUCU
Firdovsi SHARIFOV
Sayfa
104–112
Yayın Tarihi
2022-10-11
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 then investigate thenecessary and sufficient conditions on the optimality of the base in terms ofnetwork flow.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:The maximum cut problem is known to be NP-hard, and consists in deter-mining a partition of the vertices of a given graph such that the sum of theweights of the edges having one end node in each set is maximum.
📊
Temel Bulgular & Veri:In this way, we show that a greedy-like algorithm with O(mn2)time complexity finds a base of a polymatroid that is a solution to the maxi-mum cut problem with different approximation ratio.
💡
Sonuç & Katkı:We then investigate thenecessary and sufficient conditions on the optimality of the base in terms ofnetwork flow.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri

Abstract

The maximum cut problem is known to be NP-hard, and consists in deter-mining a partition of the vertices of a given graph such that the sum of theweights of the edges having one end node in each set is maximum. In thispaper, we formulate the maximum cut problem as a maximization of a simplenon-smooth convex function over the convex hull of bases of the polymatroidassociated with a submodular function defined on the subsets of vertices of agiven graph. In this way, we show that a greedy-like algorithm with O(mn2)time complexity finds a base of a polymatroid that is a solution to the maxi-mum cut problem with different approximation ratio. Moreover, with respectto a base of a polymatroid, we formulate the maximum cut problem as a max-imum flow problem between a source and a sink. We then investigate thenecessary and sufficient conditions on the optimality of the base in terms ofnetwork flow.

🔖

Bu Makaleye Atıf Yap

KUTUCU, H., SHARIFOV, F. (2022). Maximum cut problem: new models. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), Cilt: 10 - Sayı: 1, 104–112. https://ajindex.com/articles/440568

📄 Tam Metin PDF Okuyucu

📄

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

Kaynakça (18)

  1. Karp, R.M. (1972). Reducibility among combinatorial problems. In: R.E. Miller and J.W. Thatcher, eds. Complexity of Computer Computations. Plenum Press, 85-103
  2. Garey, M.R., Johnson, D.S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237-267
  3. Garey, M.R., & Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company
  4. Rendl, F., Rinaldi, G., & Wiegele, A. (2010). Solving MAX-CUT to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121(2), 307-335
  5. Boros, E., & Hammer, P.L. (2002). Pseudo- Boolean optimization. Discrete Applied Mathematics, 123(1), 155-225
  6. Goemans, M., &Williamson, D.P. (1995). Improved approximation algorithms for MAXCUT and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115-1145
  7. Bertoni, A., Campadelli, P. & Grossi, G. (2001). An approximation algorithm for the maximum cut problem and its experimental analysis. Discrete Applied Mathematics, 110(1), 3-12
  8. Ben-Ameur, W., Mahjoub, A.R., & Neto, J. (2014). The maximum cut problem. In: V.T. Paschos, ed. Paradigms of Combinatorial Optimization: Problems and New Approaches, 2nd Edition, J. Wiley and Sons, 131-172
  9. Orlova, G.I., & Dorfman, Y.G. (1972). Finding the maximum cut in a graph. Engineering Cybernetics, 10(3), 502-506
  10. Hadlock, F.O. (1975). Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3), 221-225
  11. Grötschel, M., & Pulleyblank, W.R. (1981). Weakly bipartite graphs and the max-cut problem. Operations Research Letters, 1(1), 23-27
  12. Barahona, F. (1983). The max-cut problem in graphs is not contractible to K5. Operations Research Letters, 2, 107-111
  13. Chaourar, B. (2017). A Linear Time Algorithm for a Variant of theMAX CUT Problem in Series Parallel Graphs. Advances in Operations Research, 2017, 1-4
  14. Fujishige, S. (2005). Submodular Function and Optimization. Annals of Discrete Mathematics, 2nd ed. Elsevier Science, Amsterdam
  15. Nemhauser, G. & Wolsey, L.A. (1998). Combinatorial Optimization. Wiley-Interscience, New York
  16. Iwata, S. (2008). Submodular function minimization. Mathematical Programming, 112(1), 45-64
  17. Bazaraa, M.S., Sherali, H.D., & Shetty, C.M. (2006). Nonlinear programming: Theory and Algorithms. 3rd ed. John Wiley and Sons, New York
  18. Sharifov, F.A. (2018). Find