The equipartition polytope. I: Formulations, dimension and basic facets

DOI10.1007/BF01588778zbMath0718.90092MaRDI QIDQ2639779

Yanyan Li

Publication date: 1990

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

zbMATH Keywords

cut polytope; equicut polytope; equicut; equipartition polytope; fact inducing inequalities

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

91C20: Clustering in the social and behavioral sciences

90C90: Applications of mathematical programming

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90C10: Integer programming

90C20: Quadratic programming

90C09: Boolean programming

Related Items

From equipartition to uniform cut polytopes: extended polyhedral results, Size-constrained graph partitioning polytopes, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, Min-cut clustering, A computational study of graph partitioning, Cardinality constrained Boolean quadratic polytope, A branch-and-cut algorithm for the equicut problem, Solution of large weighted equicut problems, Hamiltonian path and symmetric travelling salesman polytopes, Formulations and valid inequalities of the node capacitated graph partitioning problem, Application of cut polyhedra. I, Some new classes of facets for the equicut polytope, A projection technique for partitioning the nodes of a graph, The partition problem, A polyhedral approach for a constrained quadratic 0-1 problem, Facet-defining inequalities for the simple graph partitioning polytope, The equipartition polytope. II: Valid inequalities and facets, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A solvable case of quadratic 0-1 programming
• A polynomial characterization of some graph partitioning problems
• On the magnetisation of the ground states in two dimensional Ising spin glasses
• Facets of the Bipartite Subgraph Polytope
• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An Efficient Heuristic Procedure for Partitioning Graphs
• On the cut polytope
• Bottleneck extrema