×

zbMATH — the first resource for mathematics

Facets for the cut cone. I. (English) Zbl 0768.90074
Summary: We study facets of the cut cone \(C_ n\), i.e., the cone of dimension \({1\over 2} n(n-1)\) generated by the cuts of the complete graph on \(n\) vertices. Actually, the study of the facets of the cut cone is equivalent in some sense to the study of the facets of the cut polytope. We present several operations on facets and, in particular, a “lifting” procedure for constructing facets of \(C_{n+1}\) from given facets of the lower dimensional cone \(C_ n\). After reviewing hypermetric valid inequalities, we describe the new class of cycle inequalities and prove the facet property for several subclasses. The new class of parachute facets is developed and other known facets and valid inequalities are presented.
[For part II see the authors, ibid. 56A, No. 2, 161-188 (1992; Zbl 0768.90075)].

MSC:
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. Assouad, ”Sur les inégalités valides dansL 1,”European Journal of Combinatorics 5 (1984) 99–112. · Zbl 0549.52007
[2] P. Assouad and C. Delorme, ”Graphes plongeables dansL 1,”Comptes Rendus de l’Académie des Sciences de Paris 291 (1980) 369–372. · Zbl 0446.05020
[3] P. Assouad and M. Deza, ”Metric subspaces ofL 1,”Publications Mathématiques d’Orsay, Vol. 3 (1982). · Zbl 0478.05021
[4] D. Avis and Mutt, ”All facets of the six point Hamming cone,”European Journal of Combinatorics 10 (1989) 309–312. · Zbl 0686.52001
[5] D. Avis and M. Deza, ”The cut cone,L 1-embeddability, complexity and multicommodity flows,”Networks 21 (1991) 595–617. · Zbl 0748.90015 · doi:10.1002/net.3230210602
[6] F. Barahona, ”The max-cut problem on graphs not contractible toK 5,”Operations Research Letters 2 (1983) 107–111. · Zbl 0525.90094 · doi:10.1016/0167-6377(83)90016-0
[7] F. Barahona and M. Grötschel, ”On the cycle polytope of a binary matroid,”Journal of Combinatorial Theory B 40 (1986) 40–62. · Zbl 0596.05018 · doi:10.1016/0095-8956(86)90063-8
[8] F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, ”An application of combinatorial optimization to statistical physics and circuit layout design,”Operations Research 36(3) (1988) 493–513. · Zbl 0646.90084 · doi:10.1287/opre.36.3.493
[9] F. Barahona, M. Grötschel and A.R. Mahjoub, ”Facets of the bipartite subgraph polytope,”Mathematics of Operations Research 10 (1985) 340–358. · Zbl 0578.05056 · doi:10.1287/moor.10.2.340
[10] F. Barahona, M. Jünger and G. Reinelt, ”Experiments in quadratic 0–1 programming,”Mathematical Programming 44 (1989) 127–137. · Zbl 0677.90046 · doi:10.1007/BF01587084
[11] F. Barahona and A. R. Mahjoub, ”On the cut polytope,”Mathematical Programming 36 (1986) 157–173. · Zbl 0616.90058 · doi:10.1007/BF02592023
[12] A.E. Brower, A.M. Cohen and A. Neumaier,Distance Regular Graphs (Springer, Berlin, 1989). · Zbl 0747.05073
[13] F.C. Bussemaker, R.A. Mathon and J.J. Seidel, ”Tables of two-graphs,” TH-Report 79-WSK-05, Technical University Eindhoven (Eindhoven, Netherlands, 1979). · Zbl 0439.05032
[14] M. Conforti, M.R. Rao and A. Sassano, ”The equipartition polytope: parts I & II,”Mathematical Programming 49 (1990) 49–70, 71–91. · Zbl 0718.90092 · doi:10.1007/BF01588778
[15] C. De Simone, ”The Hamming cone, the cut polytope and the boolean quadric polytope,” preprint (1988).
[16] C. De Simone, ”The cut polytope and the boolean quadric polytope,”Discrete Mathematics 79 (1989/90) 71–75. · Zbl 0683.90068
[17] C. De Simone, M. Deza and M. Laurent, ”Collapsing and lifting for the cut cone,” Report No. 265, IASI-CNR (Roma, 1989).
[18] M. Deza, ”On the Hamming geometry of unitary cubes,”Doklady Akademii Nauk SSR 134 (1960) 1037–1040. [English translation in:Soviet Physics Doklady 5 (1961) 940–943.]
[19] M. Deza, ”Linear metric properties of binary codes,”Proceedings of the 4th Conference of USSR on Coding Theory and Transmission of Information, Moscow-Tachkent (1969) 77–85. [In Russian.]
[20] M. Deza, ”Matrices de formes quadratiques non négatives pour des arguments binaires,”Comptes Rendus de l’Académie des Sciences de Paris 277 (1973) 873–875. · Zbl 0275.05014
[21] M. Deza, ”Small pentagonal spaces,”Rendiconti del Seminario Matematico di Brescia 7 (1982) 269–282. · Zbl 0557.05059
[22] M. Deza, K. Fukuda and M. Laurent, ”The inequicut cone,” Research Report No. 89-04, GSSM, University of Tsukuba (Tokyo, 1989). · Zbl 0801.52006
[23] M. Deza, V.P. Grishukhin and M. Laurent, ”The hypermetric cone is polyhedral,” to appear in:Combinatorica. · Zbl 0801.52009
[24] M. Deza and M. Laurent, ”Facets for the cut cone II: Clique-web inequalities,”Mathematical Programming 56 (1992) 161–188, this issue. · Zbl 0768.90075 · doi:10.1007/BF01580898
[25] J. Fonlupt, A.R. Mahjoub and J-P. Uhry, ”Composition of graphs and the bipartite subgraph polytope,” to appear in:Discrete Mathematics. · Zbl 0771.05092
[26] M.R. Garey and D.S. Johnson,Computers and intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979). · Zbl 0411.68039
[27] V.P. Grishukhin, ”All facets of the cut coneC n forn=7 are known,”European Journal of Combinatorics 11 (1990) 115–117. · Zbl 0737.05074
[28] M. Grötschel and W.R. Pulleyblank, ”Weakly bipartite graphs and the max-cut problem,”Operations Research Letters 1 (1981) 23–27. · Zbl 0494.90078 · doi:10.1016/0167-6377(81)90020-1
[29] M. Grötschel and Y. Wakabayashi, ”Facets of the clique partitioning polytope,”Mathematical Programming 47 (1990) 367–387. · Zbl 0715.90092 · doi:10.1007/BF01580870
[30] F.O. Hadlock, ”Finding a maximum cut of planar graph in polynomial time,”SIAM Journal on Computing 4 (1975) 221–225. · Zbl 0321.05120 · doi:10.1137/0204019
[31] P.L. Hammer, ”Some network flow problems solved with pseudo-boolean programming,”Operations Research 13 (1965) 388–399. · Zbl 0132.13804 · doi:10.1287/opre.13.3.388
[32] A.V. Karzanov, ”Metrics and undirected cuts,”Mathematical Programming 32 (1985) 183–198. · Zbl 0565.90016 · doi:10.1007/BF01586090
[33] J.B. Kelly, ”Hypermetric spaces,”Lecture notes in Mathematics No. 490 (Springer, Berlin, 1975) pp. 17–31. · Zbl 0325.52021
[34] J.B. Kelly, unpublished.
[35] M. Padberg, ”The Boolean quadric polytope: Some characteristics, facets and relatives,”Mathematical Programming 45 (1989) 139–172. · Zbl 0675.90056 · doi:10.1007/BF01589101
[36] S. Poljak and D. Turzik, ”On a facet of the balanced subgraph polytope,”Casopis Pro Pestovani Matematiky 112 (1987) 373–380. · Zbl 0643.05059
[37] S. Poljak and D. Turzik, ”Max-cut in circulant graphs,” to appear in:Annals of Discrete Mathematics. · Zbl 0376.05053
[38] P. Terwilliger and M. Deza, ”Classification of finite connected hypermetric spaces,”Graphs and Combinatorics 3(3) (1987) 293–298. · Zbl 0618.05043 · doi:10.1007/BF01788552
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.