Maximum cut problem: new models Authors Hakan Kutucu
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.
[1] Karp, R.M. (1972). Reducibility among com- binatorial problems. In: R.E. Miller and J.W. Thatcher, eds. Complexity of Computer Com- putations. Plenum Press, 85-103.
[2] Garey, M.R., Johnson, D.S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Sci- ence, 1(3), 237-267.
[3] Garey, M.R., & Johnson, D.S. (1979). Com- puters 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 inter- secting semidefinite and polyhedral relax- ations. 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). Im- proved approximation algorithms for MAX- CUT and satisfiability problems using semi- definite 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 experimen- tal 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 Op- timization: Problems and New Approaches, 2nd Edition, J. Wiley and Sons, 131-172.
[9] Orlova, G.I., & Dorfman, Y.G. (1972). Find- ing 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¨otschel, 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. Opera- tions Research Letters, 2, 107-111.
[13] Chaourar, B. (2017). A Linear Time Algo- rithm for a Variant of the MAX CUT Problem in Series Parallel Graphs. Advances in Oper- ations Research, 2017, 1-4.
[14] Fujishige, S. (2005). Submodular Function and Optimization. Annals of Discrete Mathe- matics, 2nd ed. Elsevier Science, Amsterdam.
[15] Nemhauser, G. & Wolsey, L.A. (1998). Com- binatorial 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). Finding the maximum cut by the greedy algorithm. Cybernetics and Systems Analysis, 54(5), 737-743.