Maximum cut problem: new models

An International Journal of Optimization and Control: Theories & Applications

Hakan Kutucu¹  Firdovsi Sharifov² 

[1] Karabuk University;V.M.Glushkov Institute of Cybernetics;

关键词: Convexfunction;    bases ofpolymatroid;    submodular function;    network;   

DOI  :  10.11121/ijocta.01.2020.00826

来源: DOAJ

【 摘 要 】

In the paper, we present the maximum cut problem as maximization of a non-smooth convex function over polytope which is the convex hull of bases of the polymatroid associated with a submodular function defined on the subsets of node set of a given graph. We also formulate other new models for this problem and give necessary and enough conditions on an optimal solution in terms of network flow.

【 授权许可】

Unknown