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

DOI10.1007/BF01588778zbMath0718.90092OpenAlexW2084236013MaRDI QIDQ2639779

Yanyan Li

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1007/bf01588778

zbMATH Keywords

cut polytopeequicut polytopeequicutequipartition polytopefact inducing inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Clustering in the social and behavioral sciences (91C20) Applications of mathematical programming (90C90) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Quadratic programming (90C20) Boolean programming (90C09)

Related Items

The partition problem, A computational study of graph partitioning, Application of cut polyhedra. I, An overview of graph covering and partitioning, The equipartition polytope. II: Valid inequalities and facets, Some new classes of facets for the equicut polytope, A polyhedral approach for a constrained quadratic 0-1 problem, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, A projection technique for partitioning the nodes of a graph, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Cardinality constrained Boolean quadratic polytope, A branch-and-cut algorithm for the equicut problem, Size-constrained graph partitioning polytopes, On the polyhedral structure of uniform cut polytopes, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Facet-defining inequalities for the simple graph partitioning polytope, Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, From equipartition to uniform cut polytopes: extended polyhedral results, Hamiltonian path and symmetric travelling salesman polytopes, Formulations and valid inequalities of the node capacitated graph partitioning problem, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Min-cut clustering, Solution of large weighted equicut problems

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