Facet-defining conjecture for clique inequalities in the two-level graph partitioning polytope

Let G=(V,E)G=(V,E) be the graph and let k,kk,k' be the partition parameters, with rr, rr', and RR as defined for the corresponding clique inequalities. For a clique CC, write y(C)y(C) and z(C)z(C) for the associated clique expressions. Facet-defining conjecture. The following results hold for the convex hull of 2L-PP solutions: the yy-clique inequalities define facets if and only if r0r \ne 0; the zz-clique inequalities define facets if and only if 1<R<kk11<R<kk'-1; and the (y,z)(y,z)-clique inequalities define facets if and only if r0r'\ne 0. This conjecture would characterize exactly when the three newly studied families of clique inequalities are facet-defining, strengthening the preceding necessary conditions for non-domination; the source reports only computational evidence from PORTA, so the general assertions remain open.

Sources & referencesView supporting material

Primary source

Jamie Fairbrother, Adam Letchford and Keith Briggs, “A Two-Level Graph Partitioning Problem Arising in Mobile Wireless Communications”, arXiv:1705.08773 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.