Maximum cut problem: new models
Küçük Resim Yok
Tarih
2020
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ramazan Yaman
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
The maximum cut problem is known to be NP-hard, and consists in determining a partition of the vertices of a given graph such that the sum of the weights of the edges having one end node in each set is maximum. In this paper, we formulate the maximum cut problem as a maximization of a simple non-smooth convex function over the convex hull of bases of the polymatroid associated with a submodular function defined on the subsets of vertices of a given graph. In this way, we show that a greedy-like algorithm with O(mn(2)) time complexity finds a base of a polymatroid that is a solution to the maximum cut problem with different approximation ratio. Moreover, with respect to a base of a polymatroid, we formulate the maximum cut problem as a maximum flow problem between a source and a sink. We then investigate the necessary and sufficient conditions on the optimality of the base in terms of network flow.
Açıklama
Anahtar Kelimeler
Convex function, Bases of polymatroid, Submodular function, Network flows
Kaynak
International Journal of Optimization and Control-Theories & Applications-Ijocta
WoS Q Değeri
N/A
Scopus Q Değeri
Q3
Cilt
10
Sayı
1
