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

About 9 years old · traced to

Let G=(V,E)G=(V,E) be the graph and let k,k′k,k' be the partition parameters, with rr, r′r', 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 r≠0r \ne 0; the zz-clique inequalities define facets if and only if 1<R<kk′−11<R<kk'-1; and the (y,z)(y,z)-clique inequalities define facets if and only if r′≠0r'\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.

References

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.