Hakan KUTUCU, Firdovsi SHARIFOV

Maximum cut problem: new models

The maximum cut problem is known to be NP-hard, and consists in deter-mining a partition of the vertices of a given graph such that the sum of theweights of the edges having one end node in each set is maximum. In thispaper, we formulate the maximum cut problem as a maximization of a simplenon-smooth convex function over the convex hull of bases of the polymatroidassociated with a submodular function defined on the subsets of vertices of agiven graph. In this way, we show that a greedy-like algorithm with O(mn2)time complexity finds a base of a polymatroid that is a solution to the maxi-mum cut problem with different approximation ratio. Moreover, with respectto a base of a polymatroid, we formulate the maximum cut problem as a max-imum flow problem between a source and a sink. We then investigate thenecessary and sufficient conditions on the optimality of the base in terms ofnetwork flow.

PDF

___

[1] Karp, R.M. (1972). Reducibility among combinatorial problems. In: R.E. Miller and J.W. Thatcher, eds. Complexity of Computer Computations. Plenum Press, 85-103.
[2] Garey, M.R., Johnson, D.S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237-267.
[3] Garey, M.R., & Johnson, D.S. (1979). Computers 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 intersecting semidefinite and polyhedral relaxations. 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). Improved approximation algorithms for MAXCUT and satisfiability problems using semidefinite 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 experimental 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 Optimization: Problems and New Approaches, 2nd Edition, J. Wiley and Sons, 131-172.
[9] Orlova, G.I., & Dorfman, Y.G. (1972). Finding 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ötschel, 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. Operations Research Letters, 2, 107-111.
[13] Chaourar, B. (2017). A Linear Time Algorithm for a Variant of theMAX CUT Problem in Series Parallel Graphs. Advances in Operations Research, 2017, 1-4.
[14] Fujishige, S. (2005). Submodular Function and Optimization. Annals of Discrete Mathematics, 2nd ed. Elsevier Science, Amsterdam.
[15] Nemhauser, G. & Wolsey, L.A. (1998). Combinatorial 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.