Facets for the cut cone. II: Clique-web inequalities

DOI10.1007/BF01580898zbMath0768.90075MaRDI QIDQ1199750

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

antiwebcycle inequalitieshypermetric inequalityclique-web inequalitiesfacets for the cut conesemi-metrics

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, Facets of the \(k\)-partition polytope, Some new classes of facets for the equicut polytope, Stochastic graph partitioning: quadratic versus SOCP formulations, On the bond polytope, A polyhedral study of lifted multicuts, 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, Facets for the cut cone. I, The inequicut cone, The even and odd cut polytopes, Pseudo-Boolean optimization, The cut cone. III: On the role of triangle facets, A Lagrangian relaxation approach to the edge-weighted clique problem, The cut cone. III: On the role of triangle facets, An extended formulation approach to the edge-weighted maximal clique problem, The hypermetric cone is polyhedral, Collapsing and lifting for the cut cone, ``Miniaturized linearizations for quadratic 0/1 problems

Cites Work

• The inequicut cone
• Facets for the cut cone. I
• The hypermetric cone is polyhedral
• Collapsing and lifting for the cut cone
• The CW-inequalities for vectors in \(\ell_ 1\)
• The equipartition polytope. I: Formulations, dimension and basic facets
• Facets of the Bipartite Subgraph Polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Clique-Web Facets for Multicut Polytopes
• On the cut polytope
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item