Abstract.
We consider linear programming relaxations for the max cut problem in graphs, based on k-gonal inequalities. We show that the integrality ratio for random dense graphs is asymptotically 1+1/k and for random sparse graphs is at least 1+3/k. There are O(n k)k-gonal inequalities. These results generalize work by Poljak and Tuza, who gave similar results for k=3.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of NP-Hard problems. Proc. 27th ACM STOC 1995, 284–293
Avis, D., Grishukhin, V.P.: A bound on the k-gonality of facets of the hypermetric cone and related complexity problems. Computational Geometry: Theor. Appl. 2, 241–254 (1993)
Barahona, F., Mahjoub, A.: On the cut polytope. Math. Prog. 36, 157–173 (1986)
Chernoff, H.: A measure of the assymptotic efficiency for tests of a hypothesis based on the sum of observations. Annal. Math. Statistics 23, 493–509 (1952)
De Simone, C., Rinaldi, G.: A cutting plane algorithm for the Max-Cut problem. Optim. Method & Softw. 3, 195–214 (1994)
Deza, M.(M.E. Tylkin): Realizablility of distance matrices in unit cubes (in Russian). Problemy Kybernetiki 7, 31–42 (1962)
Deza, M., Grishukhin, V.P., Laurent, M.: The hypermetric cone is polyhedral. Combinatorica 13, 397–411 (1993)
Deza, M., Laurent, M.: Geometry of Cuts and Metrics Springer, 1997
Fujisawa, K., Kojima, M., Nakata, K.: SDPA(SemiDefinite Programming Algorithm) User's Manual – Version 5.00. Department of Mathematical and Computer Science, Tokyo Institute of Technology, Research Reports, 1999
Goemans, M., Williamson, D.: 0.878-Approximation Algorithms for MAX CUT and MAX 2SAT. Proc 26th STOC, 1994, pp. 422–431
Laurent, M., Poljak, S.: Gap inequalities for the gap polytope. Europ. J. Combinatorics 17, 233–254 (1996)
McKay, B.: Practical graph isomorphism. Congr. Numer. 30, 45–87 (1981)
Poljak, S., Tuza, Zs.: The expected relative error of the polyhedral approximation of the Max-Cut problem. Oper. Res. Lett. 16, 191–198 (1994)
Seymour, P.: Matroids and multicommodity flows. European J. Combinatorics 2, 257–290 (1981)
Van Ngoc, N., Tuza, Zs.: Linear-time Approximations of the Max-Cut Problem. In: G. Halász, D. Miklós and T. Szönyi (eds) Graphs and Numbers, Colloq. Math. Soc. János Bolyai 60, North-Holland, Amsterdam 1992, pp. 569–581
Umemoto, J.: Linear Programming Relaxations of Max-Cut. Master's Thesis, Graduate School of Informatics, Kyoto University, 2002
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Avis, D., Umemoto, J. Stronger linear programming relaxations of max-cut. Math. Program., Ser. B 97, 451–469 (2003). https://doi.org/10.1007/s10107-003-0423-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0423-5