Open AccessMaximum cut problem: new models
Author(s) -
Hakan Kutucu,
F. A. Sharifov
Publication year - 2020
Publication title -
an international journal of optimization and control theories and applications (ijocta)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.287
H-Index - 6
eISSN - 2146-5703
pISSN - 2146-0957
DOI - 10.11121/ijocta.01.2020.00826
Subject(s) - submodular set function , convex hull , mathematics , polytope , maximization , maximum cut , convex polytope , graph , combinatorics , node (physics) , maximum flow problem , mathematical optimization , regular polygon , function (biology) , set function , set (abstract data type) , convex analysis , convex optimization , computer science , geometry , structural engineering , evolutionary biology , engineering , biology , programming language
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom