scientific article; zbMATH DE number 15357
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Linear programming (90C05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
[For the entire collection see Zbl 0698.00017.] This paper extends the investigation in a previous paper of the authors [Math. Program., Ser. A 47, No. 3, 367-387 (1990; Zbl 0715.90092)]. It deals with the following problem: Let \(K_ n=(V_ n,E_ n)\) be a complete graph with \(n\) vertices. An edge set \(A\subset E_ n\) is called clique-partitioning if there exists a partition \(\{W_ 1,\dots,W_ k\}\) of the vertex set \(V_ n\) such that \(A\) is the union of all those edges in \(E_ n\) which have both endnotes in \(W_ i\) for some \(i\in\{1,\dots,k\}\). If \(c\) is a real weight function on \(E_ n\), then \(c(A)=\sum_{e\in A} c(e)\). Then the clique partition problem is to find \(A^*\) such that \(c(A^*)\) is minimal. The problem is transferred into a linear program by introducing the clique partitioning polytope \({\mathcal P}_ n\). Here the vertices of \({\mathcal P}_ n\) are in one-to-one correspondence with the cliques of \(K_ n\) and therefore the minimizing problem reduces to minimizing \(c'x\), \(x\in{\mathcal P}_ n\). The problem is of NP-type and therefore it is very unlikely that an explicit complete description can ever be obtained. The authors therefore continue to define special but large classes for which \({\mathcal P}_ n\) can be given as an intersection of half-spaces.
- Clique facets of the axial and planar assignment polytopes
- A cutting plane algorithm for a clustering problem
- Lifting theorems and facet characterization for a class of clique partitioning inequalities
- Projection results for the \(k\)-partition problem
- t-copula from the viewpoint of tail dependence matrices
- Redundant constraints in the standard formulation for the clique partitioning problem
- On the complete set packing and set partitioning polytopes: properties and rank 1 facets
- Facet-defining inequalities for the simple graph partitioning polytope
- Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
- A linear programming formulation for the maximum complete multipartite subgraph problem
- A polyhedral study of lifted multicuts
- scientific article; zbMATH DE number 36207 (Why is no real title available?)
- scientific article; zbMATH DE number 1103047 (Why is no real title available?)
- The clique partitioning problem: Facets and patching facets
- The branch and cut method for the clique partitioning problem
- A strong formulation for the graph partition problem
- \texttt{CP-Lib}: benchmark instances of the clique partitioning problem
- Binary positive semidefinite matrices and associated integer polytopes
- Chorded cycle facets of the clique partitioning polytope
- New facets of the clique partitioning polytope
- Facets of the clique partitioning polytope
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972001)
