Kutucu, HakanSharifov, Firdovsi2024-09-292024-09-2920202146-09572146-5703https://doi.org/10.11121/ijocta.01.2020.00826https://search.trdizin.gov.tr/tr/yayin/detay/378109https://hdl.handle.net/20.500.14619/6276The 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.eninfo:eu-repo/semantics/openAccessConvex functionBases of polymatroidSubmodular functionNetwork flowsArticle10.11121/ijocta.01.2020.008262-s2.0-850910876641121Q310437810910WOS:000871121500013N/A