Maximum cut problem: new models
DOI:
https://doi.org/10.11121/ijocta.01.2020.00826Keywords:
Convex function, bases of polymatroid, submodular function, networkAbstract
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.
Downloads
References
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.
Garey, M.R., Johnson, D.S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237-267.
Garey, M.R., & Johnson, D.S. (1979). Computers and Intractability: A Guide to theTheory of NP-Completeness. W.H. Freeman and Company.
Rendl, F., Rinaldi, G., & Wiegele, A. (2010). Solving MAX-CUT to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121(2), 307-335.
Boros, E., & Hammer, P.L. (2002). Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1), 155-225.
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.
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.
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.
Orlova, G.I., & Dorfman, Y.G. (1972). Finding the maximum cut in a graph. Engineering Cybernetics, 10(3), 502-506.
Hadlock, F.O. (1975). Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3), 221-225.
Gr¨otschel, M., & Pulleyblank, W.R. (1981). Weakly bipartite graphs and the max-cut problem. Operations Research Letters, 1(1), 23-27.
Barahona, F. (1983). The max-cut problem in graphs is not contractible to K5. Operations Research Letters, 2, 107-111.
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.
Fujishige, S. (2005). Submodular Function and Optimization. Annals of Discrete Mathematics, 2nd ed. Elsevier Science, Amsterdam.
Nemhauser, G. & Wolsey, L.A. (1998). Combinatorial Optimization. Wiley-Interscience, New York.
Iwata, S. (2008). Submodular function minimization. Mathematical Programming, 112(1), 45-64.
Bazaraa, M.S., Sherali, H.D., & Shetty, C.M. (2006). Nonlinear programming: Theory and Algorithms. 3rd ed. John Wiley and Sons, New York.
Sharifov, F.A. (2018). Finding the maximum cut by the greedy algorithm. Cybernetics and Systems Analysis, 54(5), 737-743.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
