Facets for the cut cone. I

DOI10.1007/BF01580897zbMath0768.90074WikidataQ56553468 ScholiaQ56553468MaRDI QIDQ1199749

Monique Laurent, Michel Marie Deza

Publication date: 16 January 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

liftingvalid inequalitiesfacetsmax-cut problemcut conecycle inequalitieshypermetric inequality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items

Application of cut polyhedra. I, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, On a positive semidefinite relaxation of the cut polytope, Facets of the \(k\)-partition polytope, The volume of relaxed Boolean-quadric and cut polytopes, Some new classes of facets for the equicut polytope, Stochastic graph partitioning: quadratic versus SOCP formulations, Lattice Points of Cut Cones, Generalised 2-circulant inequalities for the max-cut problem, Small bipartite subgraph polytopes, On the bond polytope, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, On Hilbert bases of cuts, A polyhedral study of lifted multicuts, Binary positive semidefinite matrices and associated integer polytopes, Generating facets for the cut polytope of a graph by triangular elimination, The real positive semidefinite completion problem for series-parallel graphs, Facet-defining inequalities for the simple graph partitioning polytope, Compositions in the bipartite subgraph polytope, Extension operations for cuts, Facets for the cut cone. II: Clique-web inequalities, The inequicut cone, The even and odd cut polytopes, Max-cut in circulant graphs, Pseudo-Boolean optimization, A Lagrangian relaxation approach to the edge-weighted clique problem, Checking robust nonsingularity is NP-hard, An extended formulation approach to the edge-weighted maximal clique problem, Hypercube embedding of generalized bipartite metrics, The hypermetric cone is polyhedral, \(\ell_ 1\)-rigid graphs, Collapsing and lifting for the cut cone, ``Miniaturized linearizations for quadratic 0/1 problems

Cites Work

• The max-cut problem on graphs not contractible to \(K_ 5\)
• The inequicut cone
• Facets of the clique partitioning polytope
• Sur les inégalités valides dans \(L^ 1\)
• On the cycle polytope of a binary matroid
• The classification of finite connected hypermetric spaces
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Weakly bipartite graphs and the max-cut problem
• Compositions in the bipartite subgraph polytope
• Facets for the cut cone. II: Clique-web inequalities
• All the facets of the six-point Hamming cone
• The hypermetric cone is polyhedral
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• The cut polytope and the Boolean quadric polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• Metrics and undirected cuts
• Facets of the Bipartite Subgraph Polytope
• On a facet of the balanced subgraph polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the cut polytope
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item